Solving recurrence relation for running time of combination formula I'm trying to solve the following Time complexity recurrence relation:
$T(n,k)=T(n-1,k-1)+T(n-1,k)+1$
that  come from following code:
int C(n, k) {
  if (k == 0 || k == n) return 1;  // stop recursion.
  return C(n-1, k-1) + C(n-1, k); 
}

Unfortunately, I have no idea to solve $T(n,k)$. Any hint that helpful be appreciated.
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. $$