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
