How to Do Induction Proofs

Induction is a method learned in algebra of proving something is true by taking the basic premise and proving it is true. For induction to work, your statement must be true for at least one number. The hypothesis states if it is true, at least this once it is true all the time and you prove this with the induction proof method. Prove each step with mathematical formulas.

Instructions

Difficulty: Moderately Challenging

Make Your Premise

1. State the premise that you are trying to prove. In algebra, induction proof always starts using letters so your premise looks like this:
   n²>=2n
2. Verify that your premise is true for at least one case. For example, take the premise n²>=2n where n= 2,3,...
3. Form the induction hypothesis that you want to prove. If n²>=2n then we assume it is also true for n=k, where k=2,3,..., so k²>=2k. Therefore if it is true for n=k we must now prove it is true for n=k+1.
4. Prove your induction. Now you must actually prove that your premise is true. This involves actually writing the problem out and solving it. See section two for the written problem.
5. Conclude the problem by stating your conclusions. Algebra always requires that you make a formal statement of the proof at the end of every problem you solve. Since n²>=2n and n=k+1 then (k+1)²>=2(k+1) for every (k+1)=2,3,...

Write the Problem Out

6. Take n=2 and solve for n.
7. n²>=2n
8. n²=4 2n=4 So 4>=4 and we know this works for n=2. Now we assume n=k for some integer k. We must prove that this works for n=k+1.
9. (k+1)²>=2(k+1)
10. k²+2k+2>=2k+2
11. We know k=n and n²=2n so k²=2k.
12. 2k+2k+2>= 2k+2
13. We know 2k>1 because k>1(premise n=k= 2,3,...)
14. 2k+2k+1>2k+2
    The left side is greater than right side so the induction proof is solved.