Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 2 / d / Solution

Put $H_n={\sum }_{k=0}^{\lfloor n/2\rfloor }\left(\genfrac{}{}{0ex}{}{n-k}{k}\right)$; the other summands in the printed sum vanish. The initial values are $H_0=1=F_1$ and $H_1=1=F_2$. For $n\ge 2$, Pascal's identity givesFor the first sum, when $n$ is even its final term is zero; otherwise its range already agrees with $H_{n-1}$. In the second sum put $j=k-1$, obtaining $\left(\genfrac{}{}{0ex}{}{n-2-j}{j}\right)$ for $0\le j\le \lfloor (n-2)/2\rfloor$. Thus both range identifications hold without negative upper arguments in a binomial coefficient.

Now strong induction gives $H_n=F_n+F_{n-1}=F_{n+1}$ from the two preceding cases and the Fibonacci recurrence. Hence