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