Combinatoric exercise asked in the brilliant site


Exercise:

Find the value of $\sum\limits_{i=1}^{100}{i\left( \begin{matrix}
  100 \\
  i \\
\end{matrix} \right)}$

Solution: we know that from Binomial theorem ${{\left( a+b \right)}^{n}}=\sum\limits_{i=0}^{n}{\left( \begin{matrix}
   n  \\
   i  \\
\end{matrix} \right){{a}^{n-i}}{{b}^{i}}}$

So ${{\left( x+1 \right)}^{n}}=\sum\limits_{i=0}^{n}{\left( \begin{matrix}
   n  \\
   i  \\
\end{matrix} \right){{x}^{i}}{{1}^{n-i}}\Leftrightarrow {{\left( x+1 \right)}^{100}}=\sum\limits_{i=0}^{100}{\left( \begin{matrix}
   100  \\
   i  \\
\end{matrix} \right){{x}^{i}}}}$

Now differentiating  to get , $100{{\left( x+1 \right)}^{99}}=\sum\limits_{i=0}^{100}{\left( \begin{matrix}
   100  \\
   i  \\
\end{matrix} \right)i{{x}^{i-1}}}$

Just plug $x=1$ to get $100\times {{2}^{99}}=\sum\limits_{i=0}^{100}{\left( \begin{matrix}
   100  \\
   i  \\
\end{matrix} \right)i}$

Hence $\sum\limits_{i=0}^{100}{\left( \begin{matrix}
   100  \\
   i  \\
\end{matrix} \right)i=}25\times {{2}^{101}}={{5}^{2}}\times {{2}^{101}}$

Or we can use binomial theorem $\sum\limits_{i=0}^{n}{\left( \begin{matrix}
   n  \\
   i  \\
\end{matrix} \right)={{2}^{n}}}$

So $0\left( \begin{matrix}
   n  \\
   0  \\
\end{matrix} \right)+1\left( \begin{matrix}
   n  \\
   1  \\
\end{matrix} \right)+2\left( \begin{matrix}
   n  \\
   2  \\
\end{matrix} \right)+....+n\left( \begin{matrix}
   n  \\
   n  \\
\end{matrix} \right)=\sum\limits_{i=1}^{n}{i\left( \begin{matrix}
   n  \\
   i  \\
\end{matrix} \right)}$

But $i\left( \begin{matrix}
   n  \\
   i  \\
\end{matrix} \right)=\frac{in!}{i!\left( n-i \right)!}=\frac{in!}{i\left( i-1 \right)!\left( n-i \right)!}=\frac{n\left( n-1 \right)!}{\left( i-1 \right)!\left( n-1-i+1 \right)!}=n\left( \begin{matrix}
   n-1  \\
   i-1  \\
\end{matrix} \right)$

So \(\sum\limits_{i=1}^{n}{i\left( \begin{matrix}
   n  \\
   i  \\
\end{matrix} \right)=n\sum\limits_{i=1}^{n}{\left( \begin{matrix}
   n-1  \\
   i-1  \\
\end{matrix} \right)=n{{2}^{n-1}}}}\)

So $\sum\limits_{i=1}^{100}{i\left( \begin{matrix}
   100  \\
   i  \\
\end{matrix} \right)=100\times {{2}^{99}}={{5}^{2}}\times {{2}^{101}}}$

No comments:

Post a Comment