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. 
 A: We are going to prove this with a story (i.e. counting the same in two ways).
Suppose you have $n$ favorite books and $n$ other books, ranked from good to bad:
$$ \underbrace{F_1,F_2,\dots, F_{n-1}, F_n}_{n \text{ favorite books}}\quad
\underbrace{K_1,K_2,\dots,K_{n-1},K_n}_{n\text{ ranked books}}
$$
You are going on a holiday and you want to take some ($k$, with $k\in\{0,1,2,\dots,n\}$) books with you. You must choose them from you favorite books and the best $k$ other books. The total number of ways to choose your books is $\sum_{k=0}^n{n+k\choose k}$.
Now, you could also add book $K_{n+1}$, and pick $n+1$ random books. There are $2n+1\choose n+1$ ways to do that. The worst ranked book you chose is the 'boundary', and you chose at least one ranked book, because $n+1>n$. Now, the other $n$ books are the books you are going to take with you on your holiday.
In the first case, we sum over all possible boundaries and in the second case, we just derive the boundary from the chosen subset, but the total number of ways to choose the books is the same, so we now have that
$$\sum_{k=0}^n{n+k\choose k}={2n+1\choose n+1}$$
A: 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}.$$ 
A: $\sum_{i=0}^k=\binom{n+1}{k+1}$
From here $\sum_{i=0}^n\binom{m+i}{i}=\sum_{i=0}^n\binom{m+i}{m}=\sum_{i=0}^{m+n}\binom{i}{m}= \binom{m+n+1}{m+1}=\binom{n+m+1}{n}$
In your example $m=n$ so we get $\binom{2n+1}{n+1}$
