10
$\begingroup$

I would like to evaluate:

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

Any idea?

  • 0
    @J.M. Oh cool, thanks.2011-09-03

3 Answers 3

9

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

  • 0
    @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$.2011-09-04
7

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.

3

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.