Solveeit Logo
Login

Question

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

Find the sum of ∑0≤i≤j≤n∑jnCi\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{i}}}}

Explanation

Solution

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 ∑0≤i≤j≤n∑jnCi\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
S1=∑i=0n∑j=0njnCi{{S}_{1}}=\sum\limits_{i=0}^{n}{\sum\limits_{j=0}^{n}{j{}^{n}{{C}_{i}}}}
Now, we know that ∑j=0nj=n(n+1)2\sum\limits_{j=0}^{n}{j}=\dfrac{n\left( n+1 \right)}{2} and ∑i=0nnCi=2n\sum\limits_{i=0}^{n}{{}^{n}{{C}_{i}}={{2}^{n}}}
Therefore
S1=∑i=0n∑i=0njnCi=n(n+1)22n{{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 S1{{S}_{1}} if express algebraically will be
nC01+nC02+........nC0n+{}^{n}{{C}_{0}}1+{}^{n}{{C}_{0}}2+........{}^{n}{{C}_{0}}n+
nC11+nC12+........nC1n+{}^{n}{{C}_{1}}1+{}^{n}{{C}_{1}}2+........{}^{n}{{C}_{1}}n+
. .
. .
. .
. .
nCn1+nCn2+........nCnn{}^{n}{{C}_{n}}1+{}^{n}{{C}_{n}}2+........{}^{n}{{C}_{n}}n
Now we have to find
∑0≤i≤j≤n∑jnCi\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{i}}}}
So we have to take all values of S1{{S}_{1}} in which i≤ji\le j. Also for this we have to note that the
∑0≤i≤j≤n∑jnC1=∑0≤i≤j≤n∑jnC1\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 S1{{S}_{1}} we have nC01{}^{n}{{C}_{0}}1 where i<ji< j and nCn1{}^{n}{{C}_{n}}1 where i>ji > j now
nC01{}^{n}{{C}_{0}}1, i<ji< j
nCn1{}^{n}{{C}_{n}}1, i>ji> j
Also we know that nCr=nCn−r{}^{n}{{C}_{r}}={}^{n}{{C}_{n-r}}
Therefore, nCni=nC0i{}^{n}{{C}_{n}}i={}^{n}{{C}_{0}}i
So ∑0≤i≤j≤n∑jnC1=∑n≥i≥j≥0∑jnC1\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
S2=∑0≤i≤j≤n∑jnC1{{S}_{2}}=\sum\limits_{0\le i\le j \le n}{\sum{j{}^{n}{{C}_{1}}}}
S3=∑0≤j<i≤n∑jnCi{{S}_{3}}=\sum\limits_{0\le j< i\le n}{\sum{j{}^{n}{{C}_{i}}}}
Now, we see easily that
S1=S2+S3+(nC11+nC22+.....nCnn){{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
nC11+nC22+.....+nCnn{}^{n}{{C}_{1}}1+{}^{n}{{C}_{2}}2+.....+{}^{n}{{C}_{n}}n
For this take binomial expansion of (1+x)n{{\left( 1+x \right)}^{n}}
(1+x)n=nC0+nC1x+nC2x2+.....+nCnxn{{\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(1+x)n−1=nC1+2nC2x+.....nnCnxn−1n{{\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=1x=1 above
n2n−1=nC1+2nC2+.....nnCnn{{2}^{n-1}}={}^{n}{{C}_{1}}+2{}^{n}{{C}_{2}}+.....n{}^{n}{{C}_{n}}
Now we substitute this in (2) we have
S1=S2+S3+n2n−1{{S}_{1}}={{S}_{2}}+{{S}_{3}}+n{{2}^{n-1}}
Also we know that S2=S3{{S}_{2}}={{S}_{3}} and S1{{S}_{1}} value from (1) therefore
n(n+1)2n2=2S2+n2n−1\dfrac{n\left( n+1 \right){{2}^{n}}}{2}=2{{S}_{2}}+n{{2}^{n-1}}
⇒n(n+1)2n−1−n2n−1=2S2\Rightarrow n\left( n+1 \right){{2}^{n-1}}-n{{2}^{n-1}}=2{{S}_{2}}
⇒2n−1(n2+n−n)=2S2\Rightarrow {{2}^{n-1}}\left( {{n}^{2}}+n-n \right)=2{{S}_{2}}
⇒2n−1(n2)=2S2\Rightarrow {{2}^{n-1}}\left( {{n}^{2}} \right)=2{{S}_{2}}
⇒n22n−1=2S2\Rightarrow {{n}^{2}}{{2}^{n-1}}=2{{S}_{2}} ……………………………………………..(3)
Now, we know that S2=∑0≤i<j≤n∑jnCi{{S}_{2}}=\sum\limits_{0\le i< j\le n}{\sum{j{}^{n}{{C}_{i}}}}
So, we have to add nC11+.....+nCnn{}^{n}{{C}_{1}}1+.....+{}^{n}{{C}_{n}}n in S2{{S}_{2}} to get ∑0≤i≤j≤n∑jnC1\sum\limits_{0\le i\le j\le n}{\sum{j{}^{n}{{C}_{1}}}}
Therefore
∑0≤i≤j≤n∑jnCi=S2+(nC11+nC21+.....nCnn)\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)
=n22n−2+n2n−1={{n}^{2}}{{2}^{n-2}}+n{{2}^{n-1}}
=n22n−2+n2n−1={{n}^{2}}{{2}^{n-2}}+n{{2}^{n-1}}
Hence ∑0≤i≤j≤n∑jnCi=n22n−2+n2n−1\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 (1+x)n{{\left( 1+x \right)}^{n}}.
(1+x)n=nC0+nC1x+nC2x2+.....+nCnxn{{\left( 1+x\right)}^{n}}={}^{n}{{C}_{0}}+{}^{n}{{C}_{1}}x+{}^{n}{{C}_{2}}{{x}^{2}}+.....+{}^{n}{{C}_{n}}{{x}^{n}}