finding the combinatorial sum [duplicate]

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.

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").

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.