How is $C_0^nC_n^{n+1}+ C_1^nC_{n-1}^{n}+C_2^nC_{n-2}^{n-1}+\dots+C_n^n C_0^{1} =2^{n-1}(n+2) ?$

Question

How is $$C_0^nC_n^{n+1}+ C_1^nC_{n-1}^{n}+C_2^nC_{n-2}^{n-1}+\dots+C_n^n C_0^{1} =2^n(n+2) ?$$ I have no idea how to approach this problem. There is no solution given in my book. There doesn't seem to be any pattern here. Would someone please help?

Answer 1

Hint. Note that $$C^{n+1-k}_{n-k}=\frac{(n+1-k)!}{(n-k)!1!}=(n+1-k).$$ Hence $$\begin{align} \sum_{k=0}^nC_k^{n}C_{n-k}^{n+1-k}&=(n+1)\sum_{k=0}^nC_k^{n}-\sum_{k=0}^nkC_k^{n}\\ &=(n+1)\sum_{k=0}^nC_k^{n}-n\sum_{k=1}^nC_{k-1}^{n-1}. \end{align} $$

Answer 2

Reverse the series and sum, like nine-year-old Gauss did.