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. 

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