Solving recurrence relation for running time of combination formula
Let $C(n,k) = T(n,k) + 1$. Then
$$ C(n,k) = C(n-1,k-1) + C(n-1,k). $$
This is exactly the recurrence of binomial coefficients, though there are also other solutions, for example $2^n$.
You can take the initial conditions to be $T(n,n) = T(n,0) = 1$, and so $C(n,n) = C(n,0) = 2$. You can check that
$$ C(n,k) = 2\binom{n}{k} $$
satisfies both the initial conditions and the recurrence relation. Hence
$$ T(n,k) = 2\binom{n}{k} - 1. $$