2
$\begingroup$

$n(n+1)2^{n-2} = \sum_{i=1}^ni^2\binom{n}{i}$

I had proved this combinatorially but also trying to derive this identity using binomial theorem.

From the bionomial theorem, one could easily get $2^n = \sum_{k=0}^n\binom{n}{k}$

Using this LHS could be equated with$\binom{n+1}{2}{1\over2} \sum_{k=0}^n\binom{n}{k}$

I'd like to go further to make this form closer to $\sum_{i=1}^ni^2$ but it's hard to imagine where to go.

Any advice?

$\endgroup$
1
$\begingroup$

For $i\ge0,$ $$i^2\binom ni=i(i-1)\binom ni+i\binom ni$$

Now for $i\ge1,$

$$i\binom ni=i\cdot\dfrac{n\cdot(n-1)!}{i\cdot(i-1)!\{n-1-(i-1)\}!}=n\binom{n-1}{i-1}$$

and for $i\ge2,$ $$i(i-1)\binom ni=i(i-1)\cdot\dfrac{n(n-1)\cdot(n-2)!}{i(i-1)\cdot(i-2)!\{n-2-(i-2)\}!}=n(n-1)\binom{n-2}{i-2}$$

$$\implies \sum_{i=1}^ni^2\binom ni=\binom n1+n\sum_{i=2}^n\binom{n-1}{i-1}+n(n-1)\sum_{i=2}^n\binom{n-2}{i-2}$$

Now $\displaystyle\sum_{i=2}^n\binom{n-1}{i-1}=-\binom{n-1}0+\sum_{i=1}^n\binom{n-1}{i-1}$

$\displaystyle=-1+\sum_{j=0}^{n-1}\binom{n-1}j\ \ \ \ (1)$ (setting $i-1=j$)

and $\displaystyle\sum_{i=2}^n\binom{n-2}{i-2}=\sum_{k=0}^{n-2}\binom{n-2}k\ \ \ \ (2)$ (setting $i-2=k$)

Now for integer $m\ge0,$ $$(a+b)^m=\sum_{r=0}^m\binom mra^{m-r}b^r$$

Set $a=b=1$ to find $$(1+1)^m=\sum_{r=0}^m\binom mr$$

Set $m=n-1, n-2$ for $(1),(2)$ respectively.

$\endgroup$
0
$\begingroup$

You already have $$(x+1)^n = \sum_{i=1}^n x^i{n\choose i},$$ $$n(x+1)^{n-1} = \sum_{i=1}^n i{n\choose i} x^{i-1}$$ $$nx(x+1)^{n-1} = \sum_{i=1}^n i{n\choose i} x^i$$ $$n(x+1)^{n-1} + n(n-1)x(x+1)^{n-2} = \sum_{i=1}^n i^2{n\choose i} x^{i-1}.$$

Now, taking $x=1$, you have $$n2^{n-1}+ n(n-1)2^{n-2} = \sum_{i=1}^ni^2{n \choose i}.$$

$\endgroup$
0
$\begingroup$

Let, $$(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2} x^2\cdots +\binom{n}{n} x^n$$$$$$ Differentiating wrt x, $$n(1+x)^{n-1}=\binom{n}{1}+2\binom{n}{2}x+3\binom{n}{3} x^2+\cdots +n\binom{n}{n} x^{n-1}$$$$$$ Multiplying both sides by x, $$n(1+x)^{n-1} x=\binom{n}{1}x+2\binom{n}{2}x^2+3\binom{n}{3}x^3+\cdots +n\binom{n}{n}x^n$$$$$$ Differential wrt x, $$\frac{d}{dx}(n(1+x)^{n-1}x)=\binom{n}{1}+2^2\binom{n}{2}x+3^2\binom{n}{3}x^2+\cdots +n^2\binom{n}{n} x^{n-1}$$$$$$ $$n((n-1)x(1+x)^{n-2}+(1+x)^{n-1})=\binom{n}{1}+2^2\binom{n}{2}x+3^2\binom{n}{3}x^2+\cdots +n^2\binom{n}{n} x^{n-1}$$$$$$ $$n(1+x)^{n-2}(nx+1)=\binom{n}{1}+2^2\binom{n}{2}x+3^2\binom{n}{3}x^2+\cdots +n^2\binom{n}{n} x^{n-1}$$$$$$ Put $x=1$, $$n(1+1)^{n-2}(n+1)=\binom{n}{1}+2^2\binom{n}{2}+3^2\binom{n}{3}+\cdots +n^2\binom{n}{n}$$$$$$ $$n(n+1)2^{n-2}=\binom{n}{1}+2^2\binom{n}{2}+3^2\binom{n}{3}+\cdots +n^2\binom{n}{n}$$ Hence... $$n(n+1)2^{n-2} = \sum_{i=1}^ni^2\binom{n}{i}$$

$\endgroup$
  • $\begingroup$ same${}{}{}{}{}$ $\endgroup$ – MAN-MADE Sep 22 '17 at 4:42
  • $\begingroup$ But more elaborate $\endgroup$ – neonpokharkar Sep 22 '17 at 4:43
0
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{\ell = 1}^{n}{n \choose \ell}\ell^{2} & = \sum_{\ell = 1}^{n}{n \choose \ell}\bracks{z^{2}}\pars{2!\expo{\ell z}} = 2\bracks{z}^{2}\sum_{\ell = 1}^{n}{n \choose \ell}\pars{\expo{z}}^{\ell} = 2\bracks{z}^{2}\bracks{\pars{1 + \expo{z}}^{n} - 1} \\[5mm] & = \partiald[2]{}{z}\bracks{\pars{1 + \expo{z}}^{n} - 1}_{\ z\ =\ 0} = \left. n\,\partiald{}{z}\pars{1 + \expo{z}}^{n - 1}\expo{z} \right\vert_{\ z\ =\ 0} \\[5mm] & = n\bracks{\pars{n - 1}\pars{1 + \expo{z}}^{n - 2}\expo{z} + \pars{1 + \expo{z}}^{n - 1}\expo{z}}_{\ z\ =\ 0} = n\bracks{\pars{n - 1}2^{n - 2} + 2^{n - 1}} \\[5mm] & = \bbx{n\pars{n + 1}2^{n - 2}} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.