12.2.9. Comparison of Regular and Strong Induction

Try these first

1. 1.

   What is the base case in an induction proof?

   Hint

   Think about the starting point for proving a statement.

2. 2.

   What is the inductive step?

   Hint

   How do we move from one integer to the next?

3. 3.

   What is the first step in proof by induction?

   • Prove the inductive step
   • Establish the base case
   • Conclude the proof

   Hint

   Think about which step must occur before making assumptions.

4. 4.

   True or False? Strong induction assumes that the property is true for the last case only.

   • True
   • False

   Hint

   Recall the assumption differences.

5. 5.

   Using regular induction, prove that for every positive integer n, 1 + 2 + ... + n = n(n + 1)/2.

   Hint

   Set up the algebra for LHS and simplify.

6. 6.

   Use strong induction to prove that any integer n >= 12 can be expressed as a sum of 4s and 5s.

   Hint

   Think about how to break down k + 1 into the earlier cases.