Prove that $\binom{n}{0}\binom{n+1}{n} +\binom{n}{1}\binom{n}{n-1} +\binom{n}{2}\binom{n-1}{n-2} +\cdots +\binom{n}{n}\binom{1}{0} = 2^{n-1}(n+2)$

Question

Prove the below: $$\binom{n}{0}\cdot\binom{n+1}{n} +\binom{n}{1}\cdot\binom{n}{n-1} +\binom{n}{2}\cdot\binom{n-1}{n-2} +\cdots +\binom{n}{n}\cdot\binom{1}{0} = 2^{n-1}\cdot(n+2)$$

Attempt:

Consider $$(1+x)^{n} = \binom{n}{0} + \binom{n} {1}x + \binom{n} {2}x^² + \cdots + \binom{n} {n} x^n$$

The series in the question is the coefficient of $x^n$ in $$\binom{n} {0}(1+x)^{n+1}+\binom{n} {1}x(1+x)^{n} +\binom{n} {2}x^2(1+x)^{n-1 }+ \cdots + \binom {n} {n} x^n (1+x)$$

Knowing the above, how can I rewrite the coefficient of $x^n$, as that is usually the key to solving such problems?

Answer 1

We can easily use the fact that you already observed: $$\binom{n} {0}(1+x)^{n}+\binom{n} {1}x(1+x)^{n-1} +\binom{n} {2}x^2(1+x)^{n-2}+ \cdots + \binom {n} {n} x^n=(x+(1+x))^n$$ Hence You just need the coefficient of $x^n$ in the binomial $(x+1)(2x+1)^{n},$ which is $$2^{n-1}\binom{n} {n-1}+2^n\binom{n} {n}=2^{n-1}(n+2).$$

Answer 2

Hint:

$$\binom nr\cdot\binom{n+1-r}{n-r}=\binom nr(n+1-r)=(n+1)\binom nr-r\binom nr$$

For $r\ge1,$ $$r\binom nr=n\binom{n-1}{r-1}$$

Now put $m=n,n-1$ one after another in $$(1+1)^m=\sum_{r=0}^m\binom mr$$