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.

I would like to evaluate:

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

Any idea?

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

3 Answers

up vote 9 down vote accepted

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

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

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.