Solving $f\left( n \right) = \sum\limits_{i > j \ge 0} {{}^{n + 1}{C_i}{}^n{C_j}} $

Question

My approah is as follow

Let $f\left( n \right) = \sum\limits_{i > j \ge 0} {{}^{n + 1}{C_i}{}^n{C_j}} $

$f\left( n \right) = \sum\limits_{i = i}^n {{}^{n + 1}{C_i}} \sum\limits_{j = 0}^i {{}^i{C_j}} \Rightarrow f\left( n \right) = \sum\limits_{i = i}^{n + 1} {{2^i}.{}^{n + 1}{C_i}} $

${\left( {1 + 2x} \right)^{n + 1}} = {}^{n + 1}{C_0} + {}^{n + 1}{C_1}\left( {2x} \right) + ... + {}^{n + 1}{C_{n + 1}}{\left( {2x} \right)^{n + 1}} = {3^{n + 1}}\left\{ {x = 1} \right\}$

Not able to proceed

Answer 1

The summand is the coefficient of $x^{i-j}$ from the following expression:

$$ (1+x)^{n+1}\left(1+\frac{1}{x}\right)^{n} = \frac{(1+x)^{2n+1}}{x^{n}} $$

Since $i-j>1$, we just need to sum the coefficients of $x^{n+1},...,x^{2n+1}$ from the numerator on RHS.

$$ \binom{2n+1}{n+1}+\binom{2n+1}{n+2}+...+\binom{2n+1}{2n+1}=2^{2n} $$

Seems like all the options are correct except (B)

Answer 2

Since I could not follow the nice arguments of @SamarImamZaidi exactly, I have made a somewhat more detailed derivation. This answer is only a supplement to the already existing one. We use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series. In this way we can write, for example \begin{align*} [x^k](1+x)^n=\binom{n}{k}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{f(n)}&\color{blue}{=\sum_{0\leq j<i\leq n+1}\binom{n+1}{i}\binom{n}{j}}\\ &=\sum_{j=0}^n\binom{n}{j}\sum_{i=j+1}^{n+1}\binom{n+1}{n+1-i}\tag{2}\\ &=\sum_{j=0}^{n}\binom{n}{j}\sum_{i=0}^{n-j}\binom{n+1}{n-j-i}\tag{3}\\ &=\sum_{j=0}^n\binom{n}{j}\sum_{i=0}^{n-j}[x^{n-j-i}](1+x)^{n+1}\tag{4}\\ &=[x^n](1+x)^{n+1}\sum_{j=0}^n\binom{n}{j}x^j\sum_{i=0}^{n-j}x^i\tag{5}\\ &=[x^n](1+x)^{n+1}\sum_{j=0}^n\binom{n}{j}x^j\,\frac{1-x^{n-j+1}}{1-x}\tag{6}\\ &=[x^n]\frac{(1+x)^{n+1}}{1-x}\sum_{j=0}^n\binom{n}{j}x^j\tag{7}\\ &=[x^n]\frac{(1+x)^{2n+1}}{1-x}\tag{8}\\ &=\sum_{j=0}^{n}\binom{2n+1}{j}\tag{9}\\ &\,\,\color{blue}{=2^{2n}} \end{align*} in accordance with the other answer.

Comment:

• In (2) we write the index region using two sums and apply $\binom{p}{q}=\binom{p}{p-q}$ to the inner binomial coefficient.

• In (3) we shift the index of the inner sum to start with $i=0$.

• In (4) we apply (1) to the inner binomial coefficient.

• In (5) we use the linearity of the coefficient of operator and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

• In (6) we use the finite geometric sum formula.

• In (7) we factor out $\frac{1}{1-x}$ and need only respect the term $1$ in the numerator, since the other term $x^{n-j+1}$ does not contribute to $[x^n]$.

• In (8) we apply the binomial theorem and collect equal terms.

• In (9) we have $[x^n](1+x)^{2n+1}=\binom{2n+1}{n}$ and recall that multiplication of a generating function $A(x)$ with $\frac{1}{1-x}$ gives the sum of the coefficients of $A(x)$: \begin{align*} A(x)=\sum_{n=0}^\infty \color{blue}{a_n}x^n\qquad\qquad \frac{1}{1-x}A(x)=\sum_{n=0}^\infty\left(\color{blue}{\sum_{k=0}^na_k}\right)x^n \end{align*}