How to count the number of function calls required to find $\binom{n}{r}$ using divide and conquer? This function calculates $\binom{n}{r}$ using divide and conquer and I know that the number of function calls required for calculating any $\binom{n}{r}$ is given by $2\binom{n}{r}-1$. I am looking for an explanation for this formula. How to derive this result using simple combinatorics techniques.
int binomialCoeff(int n, int k)
{
  // Base Cases
  if (k==0 || k==n)
    return 1;

  // Recurse
  return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}

 A: Since ultimately you are computing $1+1+\cdots +1$ for $\binom{n}{r}$ values of $1$, you have $\binom{n}{r}$ times where you are returning $1$, and $\binom{n}{r}-1$ times you are doing addition, so you are calling this function $2\binom{n}{r}-1$ times.
You aren't adding them sequentially in order, but you are just bracketing them. For instance, computing $\binom{4}{2}$ as:
$$((1+1)+1)+(1+(1+1))$$
So you are still doing $\binom{n}{r}-1$ additions.
A: One way to approach this is by induction.
The base cases will be both $r=0$ and $r=n$.  Now $\binom{n}{r} = 1$ in both of these cases, and there are no subfunction calls (only the top level call).  Thus the combined number of function calls is $2\binom{n}{r} - 1 = 1$.
In all other cases the function will call itself recursively twice, so in those "induction" cases $0 \lt r \lt n$ we have, besides the top level call, the calls to $n-1$ choose (resp.) $r-1$ and $r$.  Thus the number of function calls to compute $\binom{n}{r}$ in these intermediate (induction) cases is (by appealing to the induction hypothesis):
$$ 1 + (2\binom{n-1}{r-1} - 1) + (2\binom{n-1}{r} - 1)$$
A little simplification and Pascal's triangle rule gives us $2\binom{n}{r} - 1$.
To be more formal we would treat this as an induction on $n$, where the base cases $n= 0,1$ are as trivial as what I called the base case above.  In one point of view my base cases are the bordering ones of Pascal's triangle, and the counting of function calls mirrors, as Thomas Andrew's Answer outlines, the computation of entries in that triangle.
