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!

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