Menu Close

prove-that-n-N-k-0-n-k-C-2n-n-k-nC-2n-1-n-




Question Number 73046 by mathmax by abdo last updated on 05/Nov/19
prove that ∀n ∈N    Σ_(k=0) ^n  k C_(2n) ^(n+k)  =nC_(2n−1) ^n
$${prove}\:{that}\:\forall{n}\:\in{N}\:\:\:\:\sum_{{k}=\mathrm{0}} ^{{n}} \:{k}\:{C}_{\mathrm{2}{n}} ^{{n}+{k}} \:={nC}_{\mathrm{2}{n}−\mathrm{1}} ^{{n}} \\ $$
Answered by mind is power last updated on 06/Nov/19
Σ_(k=0) ^n C_(2n) ^(k+n) =Σ_(k=0) ^n C_(2n) ^(n−k) =Σ_(k=0) ^n C_(2n) ^k   Σ_(k=0) ^(k=n) C_(2n) ^(k+n) =Σ_(k=n) ^(2n) C_(2n) ^k   ⇒Σ_(k=0) ^n C_(2n) ^k +Σ_(k=n) ^(2n) C_(2n) ^k =Σ_(k=0) ^(2n) C_(2n) ^k +C_(2n) ^n =2^(2n) +C_(2n) ^n   ⇒Σ_(k=0) ^n C_(2n) ^(k+n) =2^(2n−1) +(C_(2n) ^n /2)  Σ_(k=0) ^n kC_(2n) ^(k+n) =Σ_(k=0) ^n (k+n−n)C_(2n) ^(n+k) =Σ_(k=0) ^n (k+n)C_(2n) ^(n+k) −nΣ_(k=0) ^n C_(2n) ^(k+n)   Σ(k+n)C_(2n) ^(n+k) =Σ_(k=0) ^n (k+n).((2n!)/((k+n)!.(n−k)!))  =Σ_(k=0) ^n .((2n.(2n−1)!)/((n+k−1)!.(2n−1−(n+k−1)!))=2nΣ_(k=0) ^n C_(2n−1) ^(n+k−1)   Σ_(k=0) ^n C_(2n−1) ^(n+k−1) =Σ_(k=0) ^n C_(2n−1) ^(n−k)   Σ_(k=0) ^n C_(2n−1) ^(n+k−1) +Σ_(k=0) ^n C_(2n−1) ^(n−k) =Σ_(j=0) ^(2n−1) C_(2n−1) ^j +C_(2n−1) ^n +C_(2n−1) ^(n−1)   ⇒Σ_(k=0) ^n C_(2n−1) ^(n+k−1) =(1/2)(2^(2n−1) +(C_(2n−1) ^n +C_(2n−1) ^(n−1) )  =2^(2n−2) +(C_(2n) ^n /2)  Σ(k+n)C_(2n−1) ^(n+k) =2n.(2^(n−2) +(C_(2n) ^n /2))  ⇒Σ_(k=0) ^n kC_(2n) ^(n+k) =Σ_(k=0) ^n (k+n)C_(2n) ^(n+k) −nΣ_(k=0) ^n C_(2n) ^(n+k)   =2n(2^(n−2) +(C_(2n) ^n /2))−n.(2^(n−1) +(C_(2n) ^n /2))  =(n/2).C_(2n) ^n =(n/2) C_(2n) ^n =(n/2).((2n!)/(n!.n!))=((n.2n.(2n−1)!)/(2.n.(n−1)!.n!))=((n.(2n−1)!)/(n!.(2n−1−n)!))  =nC_(2n−1) ^n   ⇒Σ_(k=0) ^n kC_(2n) ^(k+n) =nC_(2n−1) ^n
$$\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{k}+\mathrm{n}} =\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}−\mathrm{k}} =\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{k}} \\ $$$$\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{k}=\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{k}+\mathrm{n}} =\underset{\mathrm{k}=\mathrm{n}} {\overset{\mathrm{2n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{k}} \\ $$$$\Rightarrow\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{k}} +\underset{\mathrm{k}=\mathrm{n}} {\overset{\mathrm{2n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{k}} =\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{2n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{k}} +\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}} =\mathrm{2}^{\mathrm{2n}} +\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}} \\ $$$$\Rightarrow\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{k}+\mathrm{n}} =\mathrm{2}^{\mathrm{2n}−\mathrm{1}} +\frac{\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}} }{\mathrm{2}} \\ $$$$\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{kC}_{\mathrm{2n}} ^{\mathrm{k}+\mathrm{n}} =\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\left(\mathrm{k}+\mathrm{n}−\mathrm{n}\right)\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}+\mathrm{k}} =\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\left(\mathrm{k}+\mathrm{n}\right)\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}+\mathrm{k}} −\mathrm{n}\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{k}+\mathrm{n}} \\ $$$$\Sigma\left(\mathrm{k}+\mathrm{n}\right)\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}+\mathrm{k}} =\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\left(\mathrm{k}+\mathrm{n}\right).\frac{\mathrm{2n}!}{\left(\mathrm{k}+\mathrm{n}\right)!.\left(\mathrm{n}−\mathrm{k}\right)!} \\ $$$$=\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}.\frac{\mathrm{2n}.\left(\mathrm{2n}−\mathrm{1}\right)!}{\left(\mathrm{n}+\mathrm{k}−\mathrm{1}\right)!.\left(\mathrm{2n}−\mathrm{1}−\left(\mathrm{n}+\mathrm{k}−\mathrm{1}\right)!\right.}=\mathrm{2n}\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}+\mathrm{k}−\mathrm{1}} \\ $$$$\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}+\mathrm{k}−\mathrm{1}} =\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}−\mathrm{k}} \\ $$$$\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}+\mathrm{k}−\mathrm{1}} +\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}−\mathrm{k}} =\underset{\mathrm{j}=\mathrm{0}} {\overset{\mathrm{2n}−\mathrm{1}} {\sum}}\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{j}} +\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}} +\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}−\mathrm{1}} \\ $$$$\Rightarrow\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}+\mathrm{k}−\mathrm{1}} =\frac{\mathrm{1}}{\mathrm{2}}\left(\mathrm{2}^{\mathrm{2n}−\mathrm{1}} +\left(\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}} +\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}−\mathrm{1}} \right)\right. \\ $$$$=\mathrm{2}^{\mathrm{2n}−\mathrm{2}} +\frac{\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}} }{\mathrm{2}} \\ $$$$\Sigma\left(\mathrm{k}+\mathrm{n}\right)\mathrm{C}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}+\mathrm{k}} =\mathrm{2n}.\left(\mathrm{2}^{\mathrm{n}−\mathrm{2}} +\frac{\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}} }{\mathrm{2}}\right) \\ $$$$\Rightarrow\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{kC}_{\mathrm{2n}} ^{\mathrm{n}+\mathrm{k}} =\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\left(\mathrm{k}+\mathrm{n}\right)\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}+\mathrm{k}} −\mathrm{n}\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}+\mathrm{k}} \\ $$$$=\mathrm{2n}\left(\mathrm{2}^{\mathrm{n}−\mathrm{2}} +\frac{\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}} }{\mathrm{2}}\right)−\mathrm{n}.\left(\mathrm{2}^{\mathrm{n}−\mathrm{1}} +\frac{\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}} }{\mathrm{2}}\right) \\ $$$$=\frac{\mathrm{n}}{\mathrm{2}}.\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}} =\frac{\mathrm{n}}{\mathrm{2}}\:\mathrm{C}_{\mathrm{2n}} ^{\mathrm{n}} =\frac{\mathrm{n}}{\mathrm{2}}.\frac{\mathrm{2n}!}{\mathrm{n}!.\mathrm{n}!}=\frac{\mathrm{n}.\mathrm{2n}.\left(\mathrm{2n}−\mathrm{1}\right)!}{\mathrm{2}.\mathrm{n}.\left(\mathrm{n}−\mathrm{1}\right)!.\mathrm{n}!}=\frac{\mathrm{n}.\left(\mathrm{2n}−\mathrm{1}\right)!}{\mathrm{n}!.\left(\mathrm{2n}−\mathrm{1}−\mathrm{n}\right)!} \\ $$$$=\mathrm{nC}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}} \\ $$$$\Rightarrow\underset{\mathrm{k}=\mathrm{0}} {\overset{\mathrm{n}} {\sum}}\mathrm{kC}_{\mathrm{2n}} ^{\mathrm{k}+\mathrm{n}} =\mathrm{nC}_{\mathrm{2n}−\mathrm{1}} ^{\mathrm{n}} \: \\ $$$$ \\ $$

Leave a Reply

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