# Calculating $\sum_{0\le k\le n/2} \binom{n-k}{k}$

I would like to evaluate:

$$\sum_{0\le k\le n/2}\binom{n-k}{k}$$

Any idea?

-
A more general formula (equation 5.74) is derived in Concrete Mathematics; with that, the sum becomes the Binet formula for the Fibonacci numbers. –  Ｊ. Ｍ. Sep 3 '11 at 17:15
I wonder if there's a combinatorial method for this. –  Srivatsan Sep 3 '11 at 17:30
@Sri: Pages 302-303 of Concrete Mathematics has a sketch. –  Ｊ. Ｍ. Sep 3 '11 at 17:34
@J.M. Oh cool, thanks. –  Srivatsan Sep 3 '11 at 17:38

HINT

If you try a few values of $n$ you should see the pattern $$\sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n-k}{k}= F_{n+1}$$ where $F_n$ is the $n$-th Fibonacci number. With this in mind, you can employ the method of induction.

So assume there exists $n\in\mathbb{N}$ s.t $$\sum_{k=0}^{\lfloor (n-1)/2 \rfloor}\binom{n-1-k}{k}= F_n , \mbox{ and } \sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n-k}{k}=F_{n+1}$$

You want to then show $$\sum_{k=0}^{\lfloor (n-1)/2 \rfloor}\binom{n-1-k}{k} + \sum_{k=0}^{\lfloor n/2 \rfloor}\binom{n-k}{k} = \sum_{k=0}^{\lfloor (n+1)/2 \rfloor}\binom{n+1-k}{k}$$

This may appear complicated, but it becomes simple if you look at a diagram of Pascal's triangle to guide you.

Another method if via Zeckendorf's Theorem which states that every positive integer may be expressed uniquely as the sum of non-consecutive Fibonacci numbers. Notice that the sum we have counts of the number subsets of $\{ F_2, F_3, \cdots F_n \}$ without consecutive members, and the sum of the elements of each of the subsets gives integers $0, 1,2,3\cdots, F_{n+1}-1$.

-
I think you want 0,1,2,$\ldots$,$F_{n+1}-1$ for the approach via Zeckendorf's Theorem. –  Ted Sep 3 '11 at 18:55
@Ted Yes you are of course correct. I thought that it must go all the way up to $F_{n+1}$ since we could form $F_n$ with non-consecutive elements before it, then tack on the $F_n$ to form $F_{n+1}$, but of course forming $F_n$ may require $F_0 \mbox{ or } F_1$. –  Ragib Zaman Sep 4 '11 at 1:48

Ragib's answer can be formulated in a more combinatorial way:

It is well known, that $F_{n+1}$ is the number of ways that you can tile a $1\times n$ board with $1\times 2$ dominoes and $1\times 1$ squares.

$\binom{n-k}{k}$ counts such tilings that contain $k$ dominoes (and $n-2k$ squares), so the formula follows.

-

Consider the generating function $$f(z) = \sum_{n\ge 0} z^n \sum_{k=0}^{\lfloor n/2 \rfloor} {n-k\choose k}$$ and re-write it in terms of $k$ as follows $$f(z) = \sum_{k\ge 0} \sum_{\lfloor n/2 \rfloor \ge k} z^n {n-k\choose k} = \sum_{k\ge 0} \sum_{n\ge 2k} {n-k\choose k} z^n = \sum_{k\ge 0} \sum_{n\ge 0} {n+k\choose n} z^{n+2k}.$$ Now the Newton binomial can be applied to the inner sum to get $$f(z) = \sum_{k\ge 0} z^{2k} \frac{1}{(1-z)^{k+1}} = \frac{1}{1-z}\frac{1}{1-z^2/(1-z)} = \frac{1}{1-z-z^2}.$$ This is immediately seen to be the OGF of $F_{n+1}$ ($n+1$-th Fibonacci number) and we are done.

The same trick was used here at this MSE link.

-