Find a binomial term/general formula for recurrence relation We know that Pascal's triangle obeys the recurrence relation $\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k} $
And we can simply $\binom{n}{k}$ by $\frac{n!}{k!\,(n - k)!}$
I have a recurrence relation where 
$$ f(n, k) = f(n - 1, k) + f(n - 2, k - 1) $$
How can I get a generel formula for that?
Thanks in advance!
Edited:
Base Case:
$f(n, 1) = n$ and $f(n, k) = 0$ when $n < k$
 A: 
We can solve the recurrence relation using generating functions. We define
  \begin{align*}
F(x,y)=\sum_{n=0}^\infty\sum_{k=0}^\infty f(n,k)x^ny^k
\end{align*}
  find a closed expression and extract the coefficient $[x^ny^k]F(x,y)=f(n,k)$.

From the stated boundary conditions of the  recurrence   relation
\begin{align*}
f(n,k)=f(n-1,k)+f(n-2,k-1)\qquad\qquad n\geq   2, k\geq 1\tag{1}
\end{align*}
which are 
\begin{align*}
f(n,1)=1\qquad n\geq 1\\
f(n,k)=0\qquad n<k
\end{align*}
it also follows by (1)
\begin{align*}
f(n,0)=1\qquad n\geq 0
\end{align*}

We obtain
  \begin{align*}
\sum_{n=2}^\infty&\sum_{k=1}^\infty f(n,k)x^ny^k\\
&=\sum_{n=2}^\infty\sum_{k=1}^\infty f(n-1,k)x^ny^k+\sum_{n=2}^\infty\sum_{k=1}^\infty f(n-2,k-1)x^ny^k\\
&=\sum_{n=1}^\infty\sum_{k=1}^\infty f(n,k)x^{n+1}y^k+\sum_{n=0}^\infty\sum_{k=0}^\infty f(n,k)x^{n+2}y^{k+1}\\
&=x\left(F(x,y)-\sum_{n=1}^\infty f(n,0)x^{n}-\sum_{k=0}^\infty f(0,k)y^k\right)+x^2yF(x,y)\\
&=x\left(F(x,y)-\left(\frac{1}{1-x}-1\right)-1\right)+x^2yF(x,y)\\
&=(x+x^2y)F(x,y)-\frac{x}{1-x}
\end{align*}
The LHS is
  \begin{align*}
F(x,y)&-\sum_{n=2}^\infty f(n,0)x^n-\sum_{k=0}^\infty f(0,k)y^k-\sum_{k=0}^\infty f(1,k)xy^k\\
&=F(x,y)-\left(\frac{1}{1-x}-1-x\right)-1-(x+xy)\\
&=F(x,y)-\frac{1}{1-x}-xy
\end{align*}

LHS=RHS gives

\begin{align*}
F(x,y)-\frac{1}{1-x}-xy&=F(x,y)(x+x^2y)-\frac{x}{1-x}\\
F(x,y)(1-x-x^2y)&=1+xy\\
F(x,y)&=\frac{1+xy}{1-x-x^2y}
\end{align*}

In order to extract the coefficients of $F(x,y)$ we expand the generating function in powers of $x$ and $y$.

\begin{align*}
F(x,y)&=\frac{1+xy}{1-x}\cdot\frac{1}{1-\frac{x^2}{1-x}y}\\
&=\frac{1+xy}{1-x}\sum_{j=0}^\infty \left(\frac{x^2}{1-x}\right)^jy^j\\
&=\left(1+xy\right)\sum_{j=0}^\infty \frac{x^{2j}}{(1-x)^{j+1}}y^j\\
&=\left(1+xy\right)\sum_{j=0}^\infty x^{2j}\sum_{l=0}^\infty \binom{-(j+1)}{l}(-x)^ly^j\\
&=\left(1+xy\right)\sum_{j=0}^\infty x^{2j}\sum_{l=0}^\infty \binom{j+l}{l}x^ly^j\\
\end{align*}

We extract the coefficient $[x^ny^k]$ and we also use Iverson brackets 
\begin{align*}
[[P(x)]]=\begin{cases}
1&\qquad P(x) \ \text{  true}\\
0&\qquad P(x) \ \text{ false}
\end{cases}
\end{align*}
This way we can treat multiple cases in one expression.

We obtain for $0\leq k\leq n$
  \begin{align*}
[x^ny^k]F(x,y)&=[x^n][y^k]\left(1+xy\right)\sum_{j=0}^\infty x^{2j}\sum_{l=0}^\infty \binom{j+l}{l}x^ly^j\\
&=[x^n]\left([y^k]+x[y^{k-1}][[k\geq 1]]\right)\sum_{j=0}^\infty x^{2j}\sum_{l=0}^\infty \binom{j+l}{l}x^ly^j\\
&=[x^n]\left(x^{2k}\sum_{l=0}^\infty \binom{k+l}{l}x^l+ x^{2k-1}\sum_{l=0}^\infty \binom{k+l-1}{l}x^l[[k\geq 1]]\right)\\
&=\left([x^{n-2k}][[n\geq 2k]]\sum_{l=0}^\infty \binom{k+l}{l}x^l\right.\\
&\qquad\quad\left.+ [x^{n-2k+1}][[n\geq 2k-1]]\sum_{l=0}^\infty \binom{k+l-1}{l}x^l[[k\geq 1]]\right)\\
&=\binom{n-k}{n-2k}[[n\geq 2k]]+\binom{n-k}{n-2k+1}[[n\geq 2k-1]][[k\geq 1]]\\
&=\binom{n-k}{k}+\binom{n-k}{k-1}[[k\geq 1]]\\
&=\binom{n-k+1}{k}
\end{align*}
In the last two lines we use the convention $\binom{p}{q}=0$ for $0\leq p<q$.

We finally conclude

\begin{align*}
f(n,k)=\begin{cases}
\binom{n-k+1}{k}&\qquad\qquad 0\leq k<n\\
0&\qquad\qquad \text{otherwise}
\end{cases}
\end{align*}

A: Let us compute $f(n, 2)$ for any integer $n\ge2$.
First see that $$f(2, 2) =  f(1, 2) + f(0, 1) = 0$$
$$f(3, 2) =  f(2, 2) + f(1, 1) = 1$$
$$f(4, 2) =  f(3, 2) + f(2, 1) = 3$$
$$f(5, 2) =  f(4, 2) + f(3, 1) = 6$$
We can conjecture that $f(n, 2) = {(n-2)(n-1)\over2} = \sum_{k=0}^{n-2}k$
Indeed $f(2,2)$ is our base step, and if $f(n, 2) = \sum_{k=0}^{n-2}k$, then $$f(n+1) = f(n, 2) + f(n-1, 1) = \sum_{k=0}^{n-2}k + n-1 = \sum_{k=0}^{n-1}k$$
Thus $f(n, 2) = \sum_{k=0}^{n-2}k$ for all $n$.

Now compute $f(n, 3)$ for any integer $n\ge 3$ :
$$f(3, 3) =  f(2, 3) + f(1, 2) = 0$$
$$f(4, 3) =  f(3, 3) + f(2, 2) = 0$$
$$f(5, 3) =  f(4, 3) + f(3, 2) = 1$$
$$f(6, 3) =  f(5, 3) + f(4, 2) = 4$$
$$f(7, 3) =  f(6, 3) + f(5, 2) = 10$$
We have $$f(n, 3) = \sum_{i=1}^{n-2} f(i, 2) = \sum_{i=1}^{n-2}\sum_{k=1}^{i-2}k = {(n-2)(n-3)(n-4)\over6}$$

What follows is that $$f(n, k) = \sum_{i=1}^{n-2} f(i, k-1) =\sum_{i_1=1}^{n-2} \sum_{i_2=1}^{i_1-2} {\cdot \cdot \cdot} \sum_{i_{k-1}=1}^{i_{k-2}-2} i_{k-1}$$
Computing this for different values of $k$, we can conjecture that for $k\ge 3$:
$$f(n,k) = (c_k + n(n-2k-1))(n-2){(n-k-3)!\over(n-2k)!k!}$$
Where $c_k$ is a sequence of integers. Now since :
$$f(n+2,k+1) = (c_{k+1} + (n+2)(n-2k-1))n{(n-k-4)!\over(n-2k)!(k+1)!}$$
and $$f(n+1,k+1) + f(n,k) = (c_{k+1} + (n+1)(n-2k-2))(n-1){(n-k-3)!\over(n-2k-1)!(k+1)!} + (c_k + n(n-2k-1))(n-2){(n-k-3)!\over(n-2k)!k!}$$
We get : $$(n-k-3)[(c_{k+1}+(n+1)(n-2k-2))(n-1)(n-2k) + (c_k + n(n-2k-1))(n-2)(k+1)] = (c_{k+1} + (n+2)(n-2k-1))n$$
Therefore $$-(k+3)[2k(c_{k+1}-2k-2)-2(k+1)c_k] = 0$$ and thus $$c_{k+1} = {k+1\over k}c_k + 2(k+1)$$
And $c_1 = 0$

We figured : $$f(n,k) = (c_k + n(n-2k-1))(n-2){(n-k-3)!\over(n-2k)!k!}$$ where $c_1 = 0$ and $c_{k+1} = {k+1\over k}c_k + 2(k+1)$ for any natural $k$.
