Why is $\sum_{k=0}^{n} f(n,k) = F_{n+2}$? If $f(n,k)$ is the number of $k$ size subsets of $[ n ] = { 1 , \ldots , n }$ which do not contain a pair of consecutive numbers, how can I show that $\sum_{k=0}^{n} f(n,k) = F_{n+2}$?
($F_{n}$ is the nth Fibonacci number: $F_{0} = 0, F_{1} = 1, F_{n} = F_{n-1} + F_{n-2}$ for $n \geq 2$.)
Thanks!
 A: $\sum_{k=0}^nf(n,k)$ is the number of subsets of $[n]$ that do not contain two consecutive numbers, so the problem amounts to proving that there are $F_{n+2}$ such subsets. This can be proved by induction on $n$. 
To get started, note that both subsets of $[1]$ satisfy the condition, and $F_3=2$, as desired. For the induction step assume that if $1\le k\le n$, then $[k]$ has $F_{k+2}$ subsets that don’t contain consecutive integers, and consider subsets of $[n+1]$ that do not contain consecutive integers. 


*

*Some of them do not contain $n+1$, so they are subsets of $[n]$; how many of these are there?

*Some of them do contain $n+1$ and therefore do not contain $n$. If $S$ is such a subset, it must have the form $A\cup\{n+1\}$, where $A\subseteq[n-1]$; how many such sets $S$ are there?
A: Here is a solution that uses generating functions. Suppose the subsets
are  ordered with the  smallest element  first. Choosing  this element
corresponds to the generating function
$$\frac{z}{1-z}.$$
The remaining elements of the subset  are chosen by adding a series of
$k-1$ gap values $\ge 2$ consecutively starting with the first element, 
giving a contribution of
$$\left(\frac{z^2}{1-z}\right)^{k-1}.$$
Finally we need  to collect all subsets with  largest element at most
$n$, giving a factor of
$$\frac{1}{1-z}.$$
We thus have $f(n, 0)=1$ and for $k\ge 1,$
$$f(n, k) = [z^n] \frac{1}{1-z} \times \frac{z}{1-z}  \times
\left(\frac{z^2}{1-z}\right)^{k-1}
= [z^n] \frac{z^{2k-1}}{(1-z)^{k+1}}.$$
This implies for the sum that
$$\sum_{k=0}^n f(n, k) =
1 + [z^n] \sum_{k=1}^n \frac{z^{2k-1}}{(1-z)^{k+1}}
= 1 + [z^n] \frac{z}{(1-z)^2} 
\sum_{k=1}^n \frac{z^{2(k-1)}}{(1-z)^{k-1}}.$$
Putting the sum into closed form we obtain
$$1 + [z^n]  \frac{z}{(1-z)^2} 
\frac{1-(z^2/(1-z))^n}{1-z^2/(1-z)}
= 1 + [z^n] z \times 
\frac{1-(z^2/(1-z))^n}{(1-z)^2-z^2\times (1-z)}.$$
This finally yields
$$1 + [z^n]\frac{z}{1-2z+z^3}
\left(1-(z^2/(1-z))^n \right)$$
which is
$$1 + [z^n]
\left(-\frac{1}{1-z} + \frac{1+z}{1-z-z^2}\right)
\left(1-(z^2/(1-z))^n \right).$$
We proceed to coefficient extraction  and observe that the $n$th power
term starts at $z^{2n}$ and hence  no multiple of it can contribute to
$[z^n]$, leaving just two terms for coefficient extraction, the second
of which is the OGF of the Fibonacci numbers, for a final answer of
$$1 + (-1) + F_{n+1} + F_n = F_{n+2}.$$
