Question

Find the sum $\sum _{0\le i<i}^{}\sum _{j\le n}^{}{j}^n{C}_i$

Answer 1

$\sum _{0\le i}\sum _{i<j\le n}j{C}_i$

$=\sum _{r=0}^{n-1}{}^n{C}_r\{(r+1)+(r+2)+(r+3)+...+n\}$

$=\sum _{r=0}^{n-1}{}^n{C}_r\frac{(n-r)(n-r+1)}{2}$

$=\frac{1}{2}\sum _{r=0}^{n-1}{}^n{C}_r(n^2-r^2+n-r)$

$=\frac{1}{2}(n^2+n)\sum _{r=0}^{n-1}{}^n{C}_r-\frac{1}{2}\sum _{r=0}^{n-1}r{}^n{C}_r-\frac{1}{2}\sum _{r=0}^{n-1}{r}^2{}^n{C}_r$

$=\frac{1}{2}(n^2+n)(2^n-1)-\frac{1}{2}.n(2^{n-1}-1)-\frac{1}{2}n[(n-1)(2^{n-2}-1)+2^{n-1}-1]$

$=\frac{1}{2}[n^2{2}^n-n^2+n{2}^n-n-n{2}^{n-1}+n-n\{n{2}^{n-2}-n-2^{n-2}+n+2^{n-1}-1\}]$

$=\frac{1}{2}[n^2{2}^n-n^2+n{2}^n-n-n{2}^{n-1}+n-n^2{2}^{n-2}+n^2+n{2}^{n-2}-n^2-n{2}^{n-1}+n]$

$=\frac{1}{2}[n^2{2}^n+n{2}^n-n^2{2}^{n-2}-n{2}^{n-1}]$

$=\frac{1}{2}[n^2{2}^n(1-\frac{1}{4})+n{2}^n(1-\frac{1}{2})]$

$=\frac{1}{2}[n^2{2}^n\left(\frac{4-1}{4}\right)+n{2}^n\left(\frac{2-1}{2}\right)]$

$=\frac{1}{2}[n^2{2}^n\left(\frac{3}{4}\right)+n{2}^n\left(\frac{1}{2}\right)]$

$=\frac{1}{2}[n^2{2}^n\left(\frac{3}{4}\right)+n{2}^n\left(\frac{2}{4}\right)]$

$=\frac{1}{8}(3n^2+2n)2^n$

$=\frac{1}{2^3}(3n^2+2n)2^n$

$=(3n^2+2n)2^n{2}^{-3}$

$=n(3n+1)2^{n-3}$