3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You nailed it. That solved my problem. Thanks a lot. $\endgroup$ – Paulo Guilherme Inça Jan 10 at 22:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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