Prove that: $$\binom{n}0\binom{n+1}n+\binom n1\binom n{n-1}+\cdots+\binom nn\binom 10=2^{n-1}(n+2)$$
what i observed:
The sum of the lower indices in all the terms is a constant values $n$. Also the value of the sum of the upper indices in each term is decreasing by 1 and goes from $2n+1$ to $n+1$ at the end.
However i am unable to solve the problem. How do i start the problem, any hints or suggestions are welcome.
On
Using the standard notation $C^n_k=\binom{n}{k}$ your identity looks like $$\sum _{i = 0}^n\binom{n}{i}\binom{n+1-i}{n-i}=\sum _{i = 0}^n\binom{n}{i}\binom{n+1-i}{1}=\sum _{i = 0}^n\binom{n}{i}(n+1-i).$$ Hint: Use the binomial theorem for the first part and for the second one you need to know what is $\sum _{k=1}^n \binom{n}{k}\cdot k$. I suggest you write $k$ as $\binom{k}{1}$ and show that $\dbinom{a}{b}\dbinom{b}{c}=\dbinom{a}{c}\dbinom{a-c}{b-c}.$
$\mathcal{\text{Hint:}} $
$$\sum_{r=0}^n \binom{n}{r} \binom{n+1-r}{n-r} = \sum_{r=0}^n\binom nr(n+1-r) = (n+1)\sum_{r=0}^n \binom nr -\sum_{r=0}^n r\binom nr$$
The second sum may be evaluated easily because $$r\binom nr=n\binom{n-1}{r-1} $$ for $r\ge 1$.