Schreibe als Rekursionsformel

Question

Eine Zahlenfolge ist so definiert: $$a_n= \begin{cases} \sum\limits_{k=0}^{n/2}{\begin{pmatrix} n-k\\k \end{pmatrix}}, \textrm{ wenn n gerade} \\ \\ \sum\limits_{k=0}^{(n-1)/2}{\begin{pmatrix} n-k\\k \end{pmatrix}}, \textrm{ wenn n ungerade.} \end{cases}$$ Schreibe $a_n$ als Rekursionsformel ohne Summenzeichen.

Comments

hallo Roland,

es sind die Fibonacci-Zahlen. Ich suche jetzt noch einen einigermaßen eleganten Beweis ... ;-)

Answer 1

Hallo Roland,

es ist mir nicht gelungen, die Fallunterscheidung zwischen geraden und ungeraden $n$ zu beseitigen. Obwohl man $a_n$ natürlich auch schreiben kann als$$a_n = \sum\limits_{k=0}^{\lfloor n/2 \rfloor}{n-k\choose k}$$Betrachtet man zunächst die $a_n$, für das $n$ ungerade ist ... $$n \nmid 2 \implies n = 2m+1, \space \implies m=\frac{n-1}{2}$$dann ergibt sich für die Summe $a_n+a_{n+1}$:$$\begin{aligned} a_n + a_{n+1} &= \sum\limits_{k=0}^{m}{n-k \choose k} + \sum\limits_{k=0}^{m+1}{n-k+1\choose k}\\ &= \sum\limits_{k=1}^{m+1}{n-k+1 \choose k-1} + {n-k+1\choose 0} + \sum\limits_{k=1}^{m+1}{n-k+1\choose k} \\ &= {n-k+1\choose 0} + \sum\limits_{k=1}^{m+1} \left({n-k+1 \choose k-1} + {n-k+1\choose k}\right) \\ &= {n-k+1\choose 0} + \sum\limits_{k=1}^{m+1} {n+2-k\choose k} \\ &= {n+2-k\choose 0} + \sum\limits_{k=1}^{m+1} {n+2-k\choose k} \\ &= \sum\limits_{k=0}^{(n+1)/2} {n+2-k\choose k} \\ &= a_{n+2} \end{aligned}$$und nun das selbe für ein gerades $n$ $$n \mid 2 \implies n = 2m \space \implies m=\frac n2$$wieder die Summe $a_n+a_{n+1}$:$$\begin{aligned} a_n + a_{n+1} &= \sum\limits_{k=0}^{m}{n-k \choose k} + \sum\limits_{k=0}^{m}{n-k+1\choose k}\\ &= \sum\limits_{k=1}^{m+1}{n-k+1 \choose k-1} + \sum\limits_{k=0}^{m}{n-k+1\choose k} \\ &= \sum\limits_{k=1}^{m}{n-k+1 \choose k-1} + \underbrace{{n-m \choose m}}_{=1, \space \text{da}\space n-m=m}+ {n+1\choose 0} + \sum\limits_{k=1}^{m}{n-k+1\choose k} \\ &= 2+\sum\limits_{k=1}^{m}\left({n-k+1 \choose k-1}+ {n-k+1\choose k}\right)\\ &= 2+\sum\limits_{k=1}^{m}{n+2-k\choose k}\\ &= \sum\limits_{k=0}^{m+1=(n+2)/2}{n+2-k\choose k}\\ &= a_{n+2} \end{aligned}$$D.h. es gilt in jedem Fall $a_{n+2}=a_{n+1}+a_n$, es sind die Fibonacci-Zahlen mit $a_0=1$ und $a_1 =1$.

Gruß Werner

Comments

... das geht auch anders. Aber auf diese Beweisführung wäre ich nicht gekommen. Schlag nach bei Wikipedia und öffne die "Herleitung"!

---

Mit Pascal fällt einem die Lösung doch in den Schoß :

---

Mit Pascal fällt einem die Lösung doch in den Schoß

Das Bild habe ich auch als Grundlage für die obige Vorgehensweise, sonst hätte ich ja gar nicht gewußt, wie ich die Summen zerlegen muss. Aber um es als 'Beweis' formal hin zuschreiben, habe ich mich dann doch für den "Dienstweg" entschieden ;-)

---

... und wenn man weiß, nach was man suchen muss, findet man auch schicke Bildchen zum Thema. Hier eines von Hans Walser. Er nennt es die 'Schrägzeilensummen'.