finding the combinatorial sum How to find the sum of combinatorial summation of the following series, where
$C(n, k)$ denotes the number of combinations of $n$ given $k$ are the same?
$$\sum_{k=0}^{n/2} C(n-k, k)$$
Need help on this.
 A: If $s_n$ is this sum, it is easily seen from the Pascal recurrence to verify $s_{n+2}=s_n+s_{n+1}$ for all $n\in\mathbf N$, and $s_0=s_1=1$. Therefore you get the Fibonacci numbers $s_n=F_{n+1}$.
This number counts for instance the number of Morse codes of length $n$, where a dash has length $2$ (equivalently tilings of an $1\times n$ rectangle usings squares and dominoes): for some $k\leq n/2$ choose $k$ among $n-k$ points, then blow up each chosen point to a dash (adding $k$ to the length, thus making the length $n$). It also counts ways to seat people on $n-1\geq0$ successive seats without ever occupying two adjacent seats (add one seat at the end, then join each occupied seat with the next one to form a "dash").
A: Another approach is to look at the generating function
$$
\begin{align}
\sum_n\sum_k\binom{n-k}{k}x^n
&=\sum_n\sum_k\binom{n}{k}x^{n+k}\\
&=\sum_nx^n(1+x)^n\\
&=\frac1{1-x-x^2}\\
&=\frac1{\sqrt5}\left(\frac{\phi}{1-\phi x}+\frac{1/\phi}{1+x/\phi}\right)\\
&=\sum_n\frac{\phi^{n+1}-(-1/\phi)^{n+1}}{\sqrt5}x^n
\end{align}
$$
Thus,
$$
\begin{align}
\sum_k\binom{n-k}{k}
&=\frac{\phi^{n+1}-(-1/\phi)^{n+1}}{\sqrt5}\\
&=F_{n+1}
\end{align}
$$
where $F_n$ is the $n^{\text{th}}$ Fibonacci number.
