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.

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

StackExchange Computer Science Q#102667, answer score: 5