Prove the following statement by combinatorial argument.

Question

Prove the following statement by combinatorial argument:- $({n \choose0}+{n \choose1})×({n \choose1}+{n \choose2})×\cdots×({n \choose n-1}+{n \choose n})= \frac{{n \choose0}{n \choose1}{n \choose2}\cdots{n \choose n}}{n!}×(1+n)^{n} $

Well I found this question from my friend, a math lover and me too.. i thought that I could do the sum but it was confusing my mind. I am weak in making combinatorial argument so I need a help to withstand the problem so I posted here.

Answer 1

Hint:

You can use $${n\choose k-1}+{n\choose k} = {n+1\choose k}$$

and a fact that $${n+1\choose k}= {(n+1)!\over k!(n+1-k)!} $$ $$={n+1\over n+1-k }\cdot {n!\over k!(n-k)!} = {n+1\over n+1-k } {n\choose k}$$

Answer 2

What about the following for a combinatorial argument.

Let the following function be defined $$f:\mathbb{S}_n\times \binom{[n+1]}{1}\times \cdots \times \binom{[n+1]}{n}\longrightarrow \binom{[n]}{1}\times \cdots \times \binom{[n]}{n}\times [n+1]^{[n]},$$ where $[n]=\{1,2,\cdots ,n\},$ $\mathbb{S}_n$ means the group of permutations in $n$ letters and $\binom{[n]}{k}=\{ A\subseteq [n]:|A|=k \}.$

Such that $f(\pi ,A_1,\cdots ,A_n)=(A_1\cap [n],\cdots A_n\cap [n],f)$ and $f(x)=n+1$ if $n+1\in A_x$ and $f(x)=\pi _{x-g(x)}$ where $g(x)=| \{ i\in [n]:n+1\in A_i \} |.$

So, basically, this is a bijection because it has an inverse (mainly adding $n+1$ to the sets whenever you see an $n+1$ given by $f.$) and the result follows if you know that $\binom{[n+1]}{k}\equiv \binom{[n]}{k}+\binom{[n]}{k-1}$(Pascals identity.)