= Solution
Put
$$
S_n=\sum_{k=0}^{\lfloor(n-1)/2\rfloor}
\binom{n-k-1}{k}.
$$
The initial values are $S_1=S_2=1$. Using Pascal's identity and the convention that an out-of-range binomial coefficient is zero,
$$
\begin{aligned}
S_{n+2}
&=\sum_{k\geq0}\binom{n+1-k}{k}\\
&=\sum_{k\geq0}\binom{n-k}{k}
+\sum_{k\geq1}\binom{n-k}{k-1}\\
&=S_{n+1}+S_n.
\end{aligned}
$$
Thus $(S_n)$ has the same initial values and <linear recurrence relation> as the <Fibonacci numbers>. <Mathematical induction> gives
$$
\boxed{
F_n=\sum_{k=0}^{\lfloor(n-1)/2\rfloor}
\binom{n-k-1}{k}}.
$$
Back to article page
