Solving recurrence relations with two variables
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 &gt; 0$. Also, $T(n,0) = 1$ for all $n$. Applying the recurrence for all $n,k&gt;0$ and using these base cases, we get
$$
\begin{align*}
f(x,y) &amp;= \sum_{n=0}^\infty x^n + \sum_{n,k&gt;0} [T(n-1,k-1)+T(n-1,k)] x^n y^k \\ &amp;=
\sum_{n=0}^\infty x^n + \sum_{n,k} T(n,k) x^{n+1} y^{k+1} + \sum_{\substack{n \geq 0\\k&gt;0}} T(n,k) x^{n+1} y^k \\ &amp;=
\sum_{n=0}^\infty x^n + xyf(x,y) + xf(x,y) - \sum_{n=0}^\infty x^{n+1} \\ &amp;=
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 &lt; 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}$.