Question

Find the sum of \[\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{i}}}}\]

Answer 1

Hint: We will be using the concepts of the binomial theorem to solve the given question. We will be using some concepts of permutation and combination to further simplify the problem.

Complete step-by-step solution:
We have to find the sum of \[\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{i}}}}\]
Now to solve the question we will first find the value of
\[{{S}_{1}}=\sum\limits_{i=0}^{n}{\sum\limits_{j=0}^{n}{j{}^{n}{{C}_{i}}}}\]
Now, we know that \[\sum\limits_{j=0}^{n}{j}=\dfrac{n\left( n+1 \right)}{2}\] and \[\sum\limits_{i=0}^{n}{{}^{n}{{C}_{i}}={{2}^{n}}}\]
Therefore
\[{{S}_{1}}=\sum\limits_{i=0}^{n}{\sum\limits_{i=0}^{n}{j{}^{n}{{C}_{i}}}}=\dfrac{n\left( n+1 \right)}{2}{{2}^{n}}\] …………………………………………..(1)
Now, we know that sum \[{{S}_{1}}\] if express algebraically will be
\[{}^{n}{{C}_{0}}1+{}^{n}{{C}_{0}}2+........{}^{n}{{C}_{0}}n+\]
\[{}^{n}{{C}_{1}}1+{}^{n}{{C}_{1}}2+........{}^{n}{{C}_{1}}n+\]
   . .
   . .
   . .
   . .
\[{}^{n}{{C}_{n}}1+{}^{n}{{C}_{n}}2+........{}^{n}{{C}_{n}}n\]
Now we have to find
\[\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{i}}}}\]
So we have to take all values of \[{{S}_{1}}\] in which \[i\le j\]. Also for this we have to note that the
\[\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{1}}}}=\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{1}}}}\] because in the terms of \[{{S}_{1}}\] we have \[{}^{n}{{C}_{0}}1\] where \[i< j\] and \[{}^{n}{{C}_{n}}1\] where $i > j$ now
\[{}^{n}{{C}_{0}}1\], \[i< j\]
\[{}^{n}{{C}_{n}}1\], \[i> j\]
Also we know that \[{}^{n}{{C}_{r}}={}^{n}{{C}_{n-r}}\]
Therefore, \[{}^{n}{{C}_{n}}i={}^{n}{{C}_{0}}i\]
So \[\sum\limits_{0\le i\le j \le n}{\sum{j{}^{n}{{C}_{1}}}}=\sum\limits_{n\ge i\ge j\ge 0}{\sum{j{}^{n}{{C}_{1}}}}\]
Let
\[{{S}_{2}}=\sum\limits_{0\le i\le j \le n}{\sum{j{}^{n}{{C}_{1}}}}\]
\[{{S}_{3}}=\sum\limits_{0\le j< i\le n}{\sum{j{}^{n}{{C}_{i}}}}\]
Now, we see easily that
\[{{S}_{1}}={{S}_{2}}+{{S}_{3}}+\left( {}^{n}{{C}_{1}}1+{}^{n}{{C}_{2}}2+.....{}^{n}{{C}_{n}}n \right)\] ………………………………….(2)
So, we have to find value of
\[{}^{n}{{C}_{1}}1+{}^{n}{{C}_{2}}2+.....+{}^{n}{{C}_{n}}n\]
For this take binomial expansion of \[{{\left( 1+x \right)}^{n}}\]
\[{{\left( 1+x \right)}^{n}}={}^{n}{{C}_{0}}+{}^{n}{{C}_{1}}x+{}^{n}{{C}_{2}}{{x}^{2}}+.....+{}^{n}{{C}_{n}}{{x}^{n}}\]
Now we differentiate both sides w.r.t x
\[n{{\left( 1+x \right)}^{n-1}}={}^{n}{{C}_{1}}+2{}^{n}{{C}_{2}}x+.....n{}^{n}{{C}_{n}}{{x}^{n-1}}\]
Now we substitute \[x=1\] above
\[n{{2}^{n-1}}={}^{n}{{C}_{1}}+2{}^{n}{{C}_{2}}+.....n{}^{n}{{C}_{n}}\]
Now we substitute this in (2) we have
\[{{S}_{1}}={{S}_{2}}+{{S}_{3}}+n{{2}^{n-1}}\]
Also we know that \[{{S}_{2}}={{S}_{3}}\] and \[{{S}_{1}}\] value from (1) therefore
\[\dfrac{n\left( n+1 \right){{2}^{n}}}{2}=2{{S}_{2}}+n{{2}^{n-1}}\]
\[\Rightarrow n\left( n+1 \right){{2}^{n-1}}-n{{2}^{n-1}}=2{{S}_{2}}\]
\[\Rightarrow {{2}^{n-1}}\left( {{n}^{2}}+n-n \right)=2{{S}_{2}}\]
\[\Rightarrow {{2}^{n-1}}\left( {{n}^{2}} \right)=2{{S}_{2}}\]
\[\Rightarrow {{n}^{2}}{{2}^{n-1}}=2{{S}_{2}}\] ……………………………………………..(3)
Now, we know that \[{{S}_{2}}=\sum\limits_{0\le i< j\le n}{\sum{j{}^{n}{{C}_{i}}}}\]
So, we have to add \[{}^{n}{{C}_{1}}1+.....+{}^{n}{{C}_{n}}n\] in \[{{S}_{2}}\] to get \[\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{1}}}}\]
Therefore
\[\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{i}}}}={{S}_{2}}+\left( {}^{n}{{C}_{1}}1+{}^{n}{{C}_{2}}1+.....{}^{n}{{C}_{n}}n \right)\]
\[={{n}^{2}}{{2}^{n-2}}+n{{2}^{n-1}}\]
\[={{n}^{2}}{{2}^{n-2}}+n{{2}^{n-1}}\]
Hence \[\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{i}}}}={{n}^{2}}{{2}^{n-2}}+n{{2}^{n-1}}\]

Note: To solve this type of question one must have a basic understanding of the binomial theorem. Also one must remember the binomial expansion of ${{\left( 1+x \right)}^{n}}$.
${{\left( 1+x\right)}^{n}}={}^{n}{{C}_{0}}+{}^{n}{{C}_{1}}x+{}^{n}{{C}_{2}}{{x}^{2}}+.....+{}^{n}{{C}_{n}}{{x}^{n}}$