I would like to evaluate:
$\sum_{0\le k\le n/2}\binom{n-k}{k}$
Any idea?
I would like to evaluate:
$\sum_{0\le k\le n/2}\binom{n-k}{k}$
Any idea?
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 $.
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.