<s>[INST] Sum of Binomial Coefficients I am trying to find an exact formula for the following:
$\sum_{k=0}^n \binom{k+n}{k}$
Maple 16 says: $\binom{2n+1}{n+1}$
I can conclude with a induction but I would like to know if I can use a direct calculus ?
Thank you in advance. 
 [/INST] We want to choose $n+1$ numbers from the numbers $1,2,\dots,2n+1$. Clearly there are $\binom{2n+1}{n+1}$ ways to do this.
We count the number of choices in another way. First note that $\binom{k+n}{k}=\binom{n+k}{n}$.
Maybe the smallest number chosen is $n+1$. Then we must choose $n$ numbers from the remaining $n+0$. This can be done in $\binom{n+0}{n}$ ways.
Maybe the smallest number chosen is $n$. Then we must choose $n$ numbers from the remaining $n+1$ numbers. That can be done in $\binom{n+1}{n}$ ways.
Maybe the smallest number chosen is $n-1$. Then we must choose $n$ numbers from the remaining $n+2$ numbers. That can be done in $\binom{n+2}{n}$ ways.
And so on. Finally, the smallest number chosen might be $1$, in which case we must choose $n$ numbers from the remaining $n+n$. This can be done in $\binom{n+n}{n}$ ways.
More formally, let $C_k$ be the number of choices in which the smallest number chosen is $n+1-k$. Then we must choose the remaining $n$ numbers from the $n+k$ numbers greater than $n+1-k$. This can be done in $\binom{n+k}{n}=\binom{k+n}{k}$ ways. So $C_k=\binom{k+n}{k}$.
Add up from $k=0$ to $k=n$. We get that
$$\binom{2n+1}{n+1}=\sum_{k=0}^n C_k=\sum_{k=0}^n \binom{k+n}{k}.$$ 
</s>