# Solving recurrence relations with two variables

I am trying to solve this recurrence relation with two variables:

$$T(n, k) = T(n - 1, k - 1) + T(n - 1, k)$$

The base cases are:

• $$T(n, k) = 1$$ if $$k = 0$$
• $$T(n, k) = 0$$ if $$k > n$$

I was wondering if standard techniques like characteristic polynomial and generating function would work in this situation.

## 1 Answer

The standard technique is to notice that your recurrence is just Pascal's identity, and so $$T(n,k) = \binom{n}{k}$$ is a solution to the recurrence. There are other solutions, for example $$T(n,k) = 2^n$$, and multiples of both.

In your case, the binomial coefficient satisfies the initial conditions, so it is the solution.

Now, let's solve it using generating functions. Let $$f(x,y) = \sum_{n,k} T(n,k) x^n y^k.$$ The initial conditions imply that $$T(0,0) = 1$$ and $$T(0,k) = 0$$ for $$k > 0$$. Also, $$T(n,0) = 1$$ for all $$n$$. Applying the recurrence for all $$n,k>0$$ and using these base cases, we get \begin{align*} f(x,y) &= \sum_{n=0}^\infty x^n + \sum_{n,k>0} [T(n-1,k-1)+T(n-1,k)] x^n y^k \\ &= \sum_{n=0}^\infty x^n + \sum_{n,k} T(n,k) x^{n+1} y^{k+1} + \sum_{\substack{n \geq 0\\k>0}} T(n,k) x^{n+1} y^k \\ &= \sum_{n=0}^\infty x^n + xyf(x,y) + xf(x,y) - \sum_{n=0}^\infty x^{n+1} \\ &= 1 + (x+xy) f(x,y). \end{align*} Therefore $$f(x,y) = \frac{1}{1-x-xy}.$$ The coefficient of $$x^n y^k$$ is the number of walks that start at $$(0,0)$$, end at $$(n,k)$$, and at each step, either move right or diagonally. Clearly they have to move right exactly $$n-k$$ times (so if $$n < k$$ the coefficient is zero) and diagonally exactly $$k$$ times, but the order is not important. Therefore the number of walks is $$\binom{(n-k)+k}{k} = \binom{n}{k}$$.

• You nailed it. That solved my problem. Thanks a lot. Jan 10, 2019 at 22:00