Kombinatorischer Beweis und Rechnung

29.05.2009, 13:09	yalli	Auf diesen Beitrag antworten »
Kombinatorischer Beweis und Rechnung F(n)= $\begin{eqnarray} \sum_{k=0}^{[\frac {n}{2}]}~ \begin{pmatrix} n-k \\ k \end{pmatrix} \end{eqnarray}$ kann jemand für n=1,2,...,7 berechnen? und welches Bildugsgesetztz erfüllen di F(n) vermutlich?Beweis? Vielen Dank
29.05.2009, 13:14	Mazze	Auf diesen Beitrag antworten »
Eigene Ideen? Ersteres ist lediglich eine Fleissarbeit, das kannst Du sicherlich alleine. Und wenn Du die Zahlen hast sehen wir weiter
29.05.2009, 13:36	yalli	Auf diesen Beitrag antworten »
ich weiß nicht wie ich anfangen muss, es muss ein trik geben, dann wird einfacher, danke
29.05.2009, 13:54	Mazze	Auf diesen Beitrag antworten »
Der "Trick" hierbei ist einfach für n die Zahl 1 einsetzen und ausrechnen. Dann die 2 einsetzen und ausrechnen, dann die 3... bis zur 7. Und dann siehst Du es vielleicht schon.
29.05.2009, 16:54	AD	Auf diesen Beitrag antworten »
Auch wenn's zunächst nicht so aussieht: $\begin{eqnarray} F(n) \end{eqnarray}$ ist die Fibonacci-Folge mit Anfangswerten $\begin{eqnarray} F(0)=F(1)=1 \end{eqnarray}$ .
29.05.2009, 17:05	yalli	Auf diesen Beitrag antworten »
ich wusste das nicht, dass z.B für n=3 $\begin{eqnarray} {[\frac {n}{2}]} \end{eqnarray}$ =1 ist. das war sehr einfach. jetzt muss ich beweisen, dass F(n) Fibinacci ist.
Anzeige

29.05.2009, 17:25	Leopold	Auf diesen Beitrag antworten »
Nach Arthurs Beitrag genügt es, wenn du $\begin{eqnarray} F(0) \end{eqnarray}$ und $\begin{eqnarray} F(1) \end{eqnarray}$ direkt berechnest und das Rekursionsgesetz $\begin{eqnarray} F(n-1) + F(n) = F(n+1) \, , \ \ n \geq 1 \end{eqnarray}$ der Fibonacci-Folge nachweist. Fange so an: $\begin{eqnarray} F(n-1) + F(n) = \sum_{0 \leq k \leq \frac{n-1}{2}} {{n-1-k} \choose k} + \sum_{0 \leq k \leq \frac{n}{2}} {{n-k} \choose k} \end{eqnarray}$ Substituiere in der ersten Summe $\begin{eqnarray} k \end{eqnarray}$ durch $\begin{eqnarray} k-1 \end{eqnarray}$ (Indexverschiebung) und begründe, warum du dann in beiden Summen die Summationsbedingung $\begin{eqnarray} 0 \leq k \leq \frac{n+1}{2} \end{eqnarray}$ nehmen kannst. Ich gehe dabei von der erweiterten Definition der Binomialkoeffizienten aus: $\begin{eqnarray} {n \choose k} = 0 \, , \ \ \text{falls} \ k<0 \ \text{oder} \ k>n \end{eqnarray}$ Und dann ist es nur noch ein bekanntes Gesetz für Binomialkoeffizienten.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »