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 1


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.