= Solution
Put $H_n=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}$; 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\geq2$, <Pascal's identity> gives
$$
H_n=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-1-k}{k}
+\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n-1-k}{k-1}
=H_{n-1}+H_{n-2}.
$$
For 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 $\binom{n-2-j}{j}$ for $0\leq j\leq\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
$$
\boxed{\sum_{k=0}^n\binom{n-k}{k}=F_{n+1}\quad(n\geq0).}
$$
Back to article page
