Change the Recursive Relation into Formula : $f(n,k) = f(n-1,k) + f(n-2, k-1)$ I am trying to find the formula for the number $f(n,k)$ which is defined as the number of $k$-subsets of $[n]$ in which no two elements are consecutive numbers in $[n]$.
From the simple thinking I had made up following recursion:
$$f(n,k) = f(n-1,k) + f(n-2, k-1) $$
This is true since I can construct without last element of $[n]$ then make up $k$-subsets, then otherwise must contain the last element of $[n]$ then construct remaining $k-1$ elements among $[n-2]$ since with the last one, I can't use $n-1$.
However, I had never learned any techniques regarding changing those recursion into a well-summarized formula in terms of $n$ and $k$.
Any guidance would be appreciate. 
 A: We apply generating functions. Let $f(n,k) = a_{n,k}$ and let $F = \sum_{n,k \geq 0} a_{n,k} x^n y^k$. We have the reccurence $a_{n + 2, k + 1} = a_{n + 1, k + 1} + a_{n,k}$ for all $n,k \geq 0$ (we take $a_{n,k} = 0$ for $k > n$). Multiplying by $x^n y^k$ and summing we get
\begin{align}
\sum_{n \geq 0} \sum_{k \geq 0}a_{n + 2,k+1}x^ny^k = \sum_{n \geq 0} \sum_{k \geq 0}a_{n+1,k+1}x^ny^k+F
\end{align}
We simplify the right sum first. Note that $a_{n,0} = 1$. We have 
\begin{align}
\sum_{n \geq 0} \sum_{k \geq 0}a_{n + 1,k + 1} x^n y^k
&= \frac{1}{xy}\sum_{n \geq 1} \sum_{k \geq 1} a_{n,k} x^n y^k\\
&= \frac{1}{xy} \bigg(\sum_{n \geq 1} \sum_{k \geq 0} a_{n,k} x^ny^k-\sum_{n \geq 1}a_{n,0}x^n\bigg)\\
&= \frac{1}{xy} \bigg(\sum_{n \geq 1} \sum_{k \geq 0} a_{n,k} x^ny^k - \frac{x}{1- x} \bigg)\\
&= \frac{1}{xy} \bigg(F-\sum_{k \geq 0}a_{0,k} y^k - \frac{x}{1-x}\bigg)\\
&= \frac{1}{xy} (F - 1 - \frac{x}{1-x})
\end{align}
For the right hand sum we get
\begin{align}
\sum_{n \geq 0} \sum_{k \geq 0}a_{n + 1,k + 1} x^ny^k
&= \frac{1}{x^2y}\sum_{n \geq 2} \sum_{k \geq 1} x^n y^k\\
&= \frac{1}{x^2y} \bigg(\sum_{n \geq 1} \sum_{k \geq 1}x^n y^k - \sum_{k \geq 1} a_{1,k}xy^k\bigg)\\
&= \frac{1}{x^2y}\bigg(\sum_{n \geq 1} \sum_{k \geq 1}x^n y^k - xy\bigg)\\
&= \frac{1}{x^2y}\bigg(F - 1 - \frac{x}{1-x} - xy\bigg)
\end{align}
Putting this all together we get
\begin{align}
\frac{1}{x^2y}\bigg(F - 1 - \frac{x}{1-x} - xy\bigg) = F + \frac{1}{xy} (F - 1 - \frac{x}{1-x})
\end{align}
Isolating for $F$ we get
\begin{align}
F = \frac{1 + xy}{1 - x(1 + xy)} = \frac{1}{x} \frac{x(1 + xy)}{1 - x(1 + xy)}
\end{align}
Using the geometric series formula and the convention $\binom{n}{k} = 0$ for $k > n$ we get
\begin{align}
F 
&= \frac{1}{x}\sum_{n \geq 1} x^n(1 + xy)^n\\
&= \frac{1}{x}\sum_{n \geq 1} x^n \sum_{k = 0}^n \binom{n}{k} x^k y^k\\
&= \frac{1}{x}\sum_{n \geq 1} \sum_{k \geq 0} \binom{n}{k} x^{n + k}y^k\\
&= \frac{1}{x}\sum_{k \geq 0} \sum_{n \geq 1} \binom{n}{k} x^{n + k}y^k\\
&= \frac{1}{x}\sum_{k \geq 0} \sum_{n \geq k} \binom{n - k + 1}{k} y^k x^{n + 1}\\
&= \sum_{k \geq 0} \sum_{n \geq k} \binom{n - k + 1}{k} x^n y^k\\
&= \sum_{n,k \geq 0} \binom{n - k + 1}{k} x^n y^k
\end{align}
the last step follows since the binomial coefficient is zero when $n < k$. Therefore $f(n,k) = a_{n,k} = \binom{n - k + 1}{k}$.
A: Just looking at some values and arranging them in a grid (the left column corresponds to $n=0$ and the top row corresponds to $k=0$)
1   1   1   1   1   1   1   1   1   1
0   1   2   3   4   5   6   7   8   9
0   0   0   1   3   6  10  15  21  28
0   0   0   0   0   1   4  10  20  35
0   0   0   0   0   0   0   1   5  15
0   0   0   0   0   0   0   0   0   1

This looks a bit like a skew version of Pascal's triangle:
                1
             1     1
          1     2     1
       1     3     3     1
    1     4     6     4     1
 1     5    10    10     5     1

etc. It's well known that the elements of Pascal's triangle are given by $\binom{n}{k} = \frac{n!}{k!(n-k)!}$
A little manipulation of indices then shows us that the table above can be computed as:
$$
f(n,k) = \binom{n-k+1}{k} = \frac{(n-k+1)!}{k!(n-2k+1)!}
$$
A straightforward induction proof can then prove this for all $n$ and $k$.
A: $$
f(n,k)=f(n-1,k)+f(n-2,k-1) \\
f(n-1,k)=f(n-2,k)+f(n-3,k-1) \\
f(n-2,k)=f(n-3,k)+f(n-4,k-1) \\
... \\
f(2,k)=f(1,k)+f(0,k-1)
$$
We sum all expressions :
$$
f(n,k)+\sum_{p=2}^{n-1} f(p,k) = f(1,k)+\sum_{p=2}^{n-1}f(p,k) + \sum_{p=0}^{n-2} f(p,k-1)
$$
We can cancel 2 sumes :
$$
f(n,k) = f(1,k)+ \sum_{p=0}^{n-2} f(p,k-1)
$$
This can help a little bit ? Daniel
