Find a binomial term/general formula for recurrence relation

Question

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$

Answer 1

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*}

Answer 2

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