# Proofs by Induction

• Nov 29th 2010, 06:53 PM
hellfire127
Proofs by Induction[SOLVED]
Ok, I think I got most of the steps covered on these problems but can't seem to get the last part correct:

sorry, image from maple since i still have not grasp on doing the html for the symbols

i don't know if im doing the last steps correctly or not as the other problems without the summation and factorials worked fine.

Attachment 19898
• Nov 30th 2010, 12:33 AM
emakarov
In the second last line, you write $\displaystyle\sum_{i=1}^{k+2}i\cdot2^i=\sum_{i=1}^ {k+1}i\cdot2^i+k\cdot2^k$, whereas the right-hand side should be $\displaystyle\sum_{i=1}^{k+1}i\cdot2^i+(k+2)\cdot2 ^{k+2}$.

A style remark. In the beginning of the induction step, you write, "If p(k) is true for all integers k >= 2, then p(k+1) is true". First, it's helpful to write if this is your goal to prove or if you have already shown it. Second, this sentence can be interpreted as $(\forall k\ge 2.\;p(k))\to p(k+1)$, which is trivial. It is better to say, "For all k >= 2, if p(k), then p(k+1)" or "p(k) implies p(k+1) for all k >= 2".
• Nov 30th 2010, 09:49 AM
hellfire127
Quote:

Originally Posted by emakarov
In the second last line, you write $\displaystyle\sum_{i=1}^{k+2}i\cdot2^i=\sum_{i=1}^ {k+1}i\cdot2^i+k\cdot2^k$, whereas the right-hand side should be $\displaystyle\sum_{i=1}^{k+1}i\cdot2^i+(k+2)\cdot2 ^{k+2}$.

A style remark. In the beginning of the induction step, you write, "If p(k) is true for all integers k >= 2, then p(k+1) is true". First, it's helpful to write if this is your goal to prove or if you have already shown it. Second, this sentence can be interpreted as $(\forall k\ge 2.\;p(k))\to p(k+1)$, which is trivial. It is better to say, "For all k >= 2, if p(k), then p(k+1)" or "p(k) implies p(k+1) for all k >= 2".

ok i understand that part now. so the second problem should have be [(k+1)!-1]+(k+1)(k+1!). how do you simply this and the first problem to show that they equal p(k+1)?
• Nov 30th 2010, 10:11 AM
emakarov
Quote:

so the second problem should have be [(k+1)!-1]+(k+1)(k+1!). how do you simply this and the first problem to show that they equal p(k+1)?
[(k+1)!-1]+(k+1)(k+1!) = (k + 1)! * (1 + k + 1) - 1 = (k+2)! - 1. In the first problem you similarly factor out $2^{k+2}$.