Prove the following statement by combinatorial argument. 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.
 A: 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}$$
A: 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.)
