Use combinatorial arguments to prove the following binomial identities

Question

Can anyone help prove this binomial identities by using the combinatorial arguments, I have no clue to get start. Thanks. $$\binom{2n+1}{n}=\sum_{k=0}^{n}\binom{n+k}{k}$$

Answer 1

The number of lattice paths from $(0,0)$ to $(n+1,n)$ consisting of $(1,0)$-steps and $(0,1)$-steps is $$\binom{2n+1}{n}=\binom{2n+1}{n+1}$$ since we have to choose precisely $n+1$ $(1,0)$-steps out of $2n+1$ steps.

                               

Each of these paths crosses the vertical line $x=n$ at a specific height $k$ with $0\leq k\leq n$. There are $$\binom{n+k}{k}$$ paths crossing the vertical line $x=n$ at height $k$. Since this holds for each $0\leq k\leq n$

we conclude

\begin{align*} \color{blue}{\sum_{k=0}^n\binom{n+k}{k}=\binom{2n+1}{n}} \end{align*}

Answer 2

You can write your formula like: $\binom{2n+1}{n+1}=\sum_{k=0}^{n}\binom{n+k}{n} $ Let $A$ be set , $\left| A \right|=2n+1$,and we can interpret left side like all subsets $B \subset A$, $\left| B \right|=n+1$. We can easily note that in every $B$ greatest element is at least $n+1$.Now family of all subsets $B$ we can divide into n+1 parts.
first part: all $B$ subsets in which $n+1$ is greatest element
second part:all $B$ subsets in which $n+2$ is greatest element.
....
(n+1)-th part:all $B$ subsets in which $2n+1$ is greatest element Note that all parts are disjoint.
$\rightarrow$Cardinal number of first part is $\binom{n}{n}$ because we can only use elements smaller than $n+1$ $\rightarrow$Cardinal number of second part is $\binom{n+1}{n}$ because we can only use elements smaller than $n+2$
...
$\rightarrow$Cardinal number of (n+1)-th part is $\binom{2n}{n}$ because we can only use elements smaller than $2n+1$
Thus,right side is $\sum_{k=0}^{n}\binom{n+k}{n}$ We conclude: $$ \binom{2n+1}{n+1}=\sum_{k=0}^{n}\binom{n+k}{n} $$