Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

2 Answers

up vote 5 down vote accepted

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

share|improve this answer
Just awesome :) –  Chaitanya Feb 2 '13 at 18:19
add comment

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.

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.