Saved Bookmarks
| 1. |
Prove by mathematical induction that `sum_(r=0)^(n)r^(n)C_(r)=n.2^(n-1), forall n in N`. |
|
Answer» Let `P(n):sum_(r=0)^(n)r^(n)C_(r)=n.2^(n-1)` Step I For n=1, LHS of Eq. (i) `=sum_(r=0)^(1)r.^(1)C_(r)=0+1.^(1)C_(1)=1` and RHS of Eq. (i) `=1.2^(1-1)=2^(0)=1` Therefore , P(1) is true . Step II Assume that P(k) is true , then P(k) : `sum_(r=0)^(k)r.^(k)C_(r)=k.2^(k-1)` Step III For `n=k+1` `P(k+1):sum_(r=0)^(k+1)r.^(k+1)C_(r)=(k+1).2^(k)` `therefore LHS =sum_(r=0)^(k+1)r.^(k+1)C_(r)=0+sum_(r=1)^(k+1)r.^(k+1)C_(r)` `=sum_(r=1)^(k+1)r.^(k+1)C_(r)=sum_9r=1)^(k)r.^(k+1)C_(r)+(k+1).^(k+1)C_(k+1)` `=sum_(r=1)^(k)r(.^(k)C_(r)+.^(k)C_(r-1))+(k+1)` `=sum_(r=1)^(k)r.^(k)C_(r)+sum_(r=0)^(k)r.^(k)C_(r-1)+(k+1)` `=sum_(r=0)^(k)r.^(k)C_(r)+sum_(r=0)^(k+1)r.^(k)C_(r-1)` `=sum_(r=0)^(k)r.^(k)C_(r)+sum _(r=0)^(k)(r+1).^(k)C_r)` `=sum_(r=0)^(k)r.^(k)C_(r)+sum_(r=0)^(k)r.^(k)C_(r)+sum_(r=0)^(k).^(k)C_(r)` `=P(k)+P(k)+2^k` [by assumption step] `=k.2^(k-1)+k.26(k-1)+2^(k)=2.k.2^k-1+2^k` `=k.2^k+2^k=(k+1).2^k=RHS` Therefore , `P(k+1)` is true. Hence , by the principle of mathematical induction `P(n)` is true for all `n in N`. |
|