# 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.

-

## marked as duplicate by Grigory M, Sanath K. Devalapurkar, amWhy, mau, user63181 May 20 '14 at 15:45

Is it $n/2$ rounded down if needed (floor function)? – Maesumi Feb 2 '13 at 18:06
Even, I am confused. :( – Chaitanya Feb 2 '13 at 18:08
Well, my question is mute. It does not make a difference because when you are above n/2 the binomial coefficient is zero anyway. Marc's answer covers all cases. – Maesumi Feb 2 '13 at 18:14

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

-
Just awesome :) – Chaitanya Feb 2 '13 at 18:19

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.

-
Sorry, I am not able to up because of my reputation. What ever thanks :) – Chaitanya Feb 3 '13 at 8:36
@Chaitanya: actually, now you can :-) – robjohn Feb 3 '13 at 11:59
Cool. Now, actually I did. :D – Chaitanya Feb 3 '13 at 12:08