Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new 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
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|cite|improve this answer
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.

share|cite|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

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