Menu Close

find-interms-of-n-the-sum-k-0-n-k-2-C-n-k-




Question Number 33074 by prof Abdo imad last updated on 10/Apr/18
find interms of n  the sum Σ_(k=0) ^n  k^2   C_n ^k
$${find}\:{interms}\:{of}\:{n}\:\:{the}\:{sum}\:\sum_{{k}=\mathrm{0}} ^{{n}} \:{k}^{\mathrm{2}} \:\:{C}_{{n}} ^{{k}} \\ $$
Commented by abdo imad last updated on 10/Apr/18
let consider the polynom p(x)= Σ_(k=0) ^n   C_n ^k   x^k   we know that p(x)= (x+1)^n   ⇒p^′ (x)=n(x+1)^(n−1) ⇒  p^(′′) (x) =n(n−1)(x+1)^(n−2)   from another side  p^′ (x)= Σ_(k=1) ^n  k C_n ^k   x^(k−1)   and  p^(′′) (x) = Σ_(k=2) ^n  k(k−1) C_n ^k  x^(k−2)   = Σ_(k=2) ^n  k^2  C_n ^k  x^(k−2)   −Σ_(k=2) ^n k C_n ^k  x^(k−2)   ⇒Σ_(k=2) ^n  k^2  C_n ^k  x^(k−2) = p^(′′) (x) + Σ_(k=2) ^n  k C_n ^k  x^(k−2)   x=1⇒ Σ_(k=2) ^n  k^2  C_n ^k   =p^(′′) (1) + Σ_(k=2) ^n  k C_n ^k   =n(n−1) 2^(n−2)   +n 2^(n−1)  −1 ⇒  Σ_(k=1) ^n   k^2   C_n ^k    = n(n−1)2^(n−2)    +n 2^(n−1)   .  =(n^2 −n) 2^(n−2)   + 2n 2^(n−2)   =(n^2  +n) 2^(n−2)   .  Σ_(k=1) ^n   k^2  C_n ^k   = (n^2  +n) 2^(n−2)    .
$${let}\:{consider}\:{the}\:{polynom}\:{p}\left({x}\right)=\:\sum_{{k}=\mathrm{0}} ^{{n}} \:\:{C}_{{n}} ^{{k}} \:\:{x}^{{k}} \\ $$$${we}\:{know}\:{that}\:{p}\left({x}\right)=\:\left({x}+\mathrm{1}\right)^{{n}} \:\:\Rightarrow{p}^{'} \left({x}\right)={n}\left({x}+\mathrm{1}\right)^{{n}−\mathrm{1}} \Rightarrow \\ $$$${p}^{''} \left({x}\right)\:={n}\left({n}−\mathrm{1}\right)\left({x}+\mathrm{1}\right)^{{n}−\mathrm{2}} \:\:{from}\:{another}\:{side} \\ $$$${p}^{'} \left({x}\right)=\:\sum_{{k}=\mathrm{1}} ^{{n}} \:{k}\:{C}_{{n}} ^{{k}} \:\:{x}^{{k}−\mathrm{1}} \:\:{and} \\ $$$${p}^{''} \left({x}\right)\:=\:\sum_{{k}=\mathrm{2}} ^{{n}} \:{k}\left({k}−\mathrm{1}\right)\:{C}_{{n}} ^{{k}} \:{x}^{{k}−\mathrm{2}} \:\:=\:\sum_{{k}=\mathrm{2}} ^{{n}} \:{k}^{\mathrm{2}} \:{C}_{{n}} ^{{k}} \:{x}^{{k}−\mathrm{2}} \:\:−\sum_{{k}=\mathrm{2}} ^{{n}} {k}\:{C}_{{n}} ^{{k}} \:{x}^{{k}−\mathrm{2}} \\ $$$$\Rightarrow\sum_{{k}=\mathrm{2}} ^{{n}} \:{k}^{\mathrm{2}} \:{C}_{{n}} ^{{k}} \:{x}^{{k}−\mathrm{2}} =\:{p}^{''} \left({x}\right)\:+\:\sum_{{k}=\mathrm{2}} ^{{n}} \:{k}\:{C}_{{n}} ^{{k}} \:{x}^{{k}−\mathrm{2}} \\ $$$${x}=\mathrm{1}\Rightarrow\:\sum_{{k}=\mathrm{2}} ^{{n}} \:{k}^{\mathrm{2}} \:{C}_{{n}} ^{{k}} \:\:={p}^{''} \left(\mathrm{1}\right)\:+\:\sum_{{k}=\mathrm{2}} ^{{n}} \:{k}\:{C}_{{n}} ^{{k}} \\ $$$$={n}\left({n}−\mathrm{1}\right)\:\mathrm{2}^{{n}−\mathrm{2}} \:\:+{n}\:\mathrm{2}^{{n}−\mathrm{1}} \:−\mathrm{1}\:\Rightarrow \\ $$$$\sum_{{k}=\mathrm{1}} ^{{n}} \:\:{k}^{\mathrm{2}} \:\:{C}_{{n}} ^{{k}} \:\:\:=\:{n}\left({n}−\mathrm{1}\right)\mathrm{2}^{{n}−\mathrm{2}} \:\:\:+{n}\:\mathrm{2}^{{n}−\mathrm{1}} \:\:. \\ $$$$=\left({n}^{\mathrm{2}} −{n}\right)\:\mathrm{2}^{{n}−\mathrm{2}} \:\:+\:\mathrm{2}{n}\:\mathrm{2}^{{n}−\mathrm{2}} \:\:=\left({n}^{\mathrm{2}} \:+{n}\right)\:\mathrm{2}^{{n}−\mathrm{2}} \:\:. \\ $$$$\sum_{{k}=\mathrm{1}} ^{{n}} \:\:{k}^{\mathrm{2}} \:{C}_{{n}} ^{{k}} \:\:=\:\left({n}^{\mathrm{2}} \:+{n}\right)\:\mathrm{2}^{{n}−\mathrm{2}} \:\:\:. \\ $$
Answered by sma3l2996 last updated on 10/Apr/18
Σ_(k=0) ^n k^2 ^n C_k =??  k^2 ^n C_k =k×k^n C_k =k×n^(n−1) C_(k−1)   so  Σ_(k=0) ^n k^2 ^n C_k =nΣ_(k=1) ^n k ^(n−1) C_(k−1)   let  l=k−1  Σ_(k=1) ^n k ^(n−1) C_(k−1) =Σ_(l=0) ^(n−1) (l+1)^(n−1) C_l   =Σ_(l=0) ^(n−1) l ^(n−1) C_l +Σ_(l=0) ^(n−1) ^(n−1) C_l   we already knew  that  Σ_(k=0) ^n  ^n C_k =2^n   and  Σ_(l=0) ^n l ^n C_l =2^(n−1) n   (check  Q 33072)  So  Σ_(k=0) ^n k^2 ^n C_k =n(Σ_(k=0) ^(n−1) k ^(n−1) C_k +Σ_(k=0) ^(n−1) ^(n−1) C_k )  =n(2^(n−2) (n−1)+2^(n−1) )  Σ_(k=0) ^n k^2 ^n C_k =2^(n−2) n(n+1)
$$\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}{k}^{\mathrm{2}} \:^{{n}} {C}_{{k}} =?? \\ $$$${k}^{\mathrm{2}} \:^{{n}} {C}_{{k}} ={k}×{k}\:^{{n}} {C}_{{k}} ={k}×{n}\:^{{n}−\mathrm{1}} {C}_{{k}−\mathrm{1}} \\ $$$${so}\:\:\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}{k}^{\mathrm{2}} \:^{{n}} {C}_{{k}} ={n}\underset{{k}=\mathrm{1}} {\overset{{n}} {\sum}}{k}\:\:^{{n}−\mathrm{1}} {C}_{{k}−\mathrm{1}} \\ $$$${let}\:\:{l}={k}−\mathrm{1} \\ $$$$\underset{{k}=\mathrm{1}} {\overset{{n}} {\sum}}{k}\:\:^{{n}−\mathrm{1}} {C}_{{k}−\mathrm{1}} =\underset{{l}=\mathrm{0}} {\overset{{n}−\mathrm{1}} {\sum}}\left({l}+\mathrm{1}\right)\:^{{n}−\mathrm{1}} {C}_{{l}} \\ $$$$=\underset{{l}=\mathrm{0}} {\overset{{n}−\mathrm{1}} {\sum}}{l}\:\:^{{n}−\mathrm{1}} {C}_{{l}} +\underset{{l}=\mathrm{0}} {\overset{{n}−\mathrm{1}} {\sum}}\:^{{n}−\mathrm{1}} {C}_{{l}} \\ $$$${we}\:{already}\:{knew}\:\:{that}\:\:\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}\:\:^{{n}} {C}_{{k}} =\mathrm{2}^{{n}} \\ $$$${and}\:\:\underset{{l}=\mathrm{0}} {\overset{{n}} {\sum}}{l}\:\:^{{n}} {C}_{{l}} =\mathrm{2}^{{n}−\mathrm{1}} {n}\:\:\:\left({check}\:\:{Q}\:\mathrm{33072}\right) \\ $$$${So}\:\:\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}{k}^{\mathrm{2}} \:^{{n}} {C}_{{k}} ={n}\left(\underset{{k}=\mathrm{0}} {\overset{{n}−\mathrm{1}} {\sum}}{k}\:\:^{{n}−\mathrm{1}} {C}_{{k}} +\underset{{k}=\mathrm{0}} {\overset{{n}−\mathrm{1}} {\sum}}\:^{{n}−\mathrm{1}} {C}_{{k}} \right) \\ $$$$={n}\left(\mathrm{2}^{{n}−\mathrm{2}} \left({n}−\mathrm{1}\right)+\mathrm{2}^{{n}−\mathrm{1}} \right) \\ $$$$\underset{{k}=\mathrm{0}} {\overset{{n}} {\sum}}{k}^{\mathrm{2}} \:^{{n}} {C}_{{k}} =\mathrm{2}^{{n}−\mathrm{2}} {n}\left({n}+\mathrm{1}\right) \\ $$

Leave a Reply

Your email address will not be published. Required fields are marked *