12.2. Induction

Try these first

1. 1.

   What is the base case in proof by induction?

   Hint

   Think of the first value where the property must hold true.

2. 2.

   What must be proven in the inductive step?

   Hint

   Consider what happens when you move to the next number.

3. 3.

   What is the first step in proof by induction?

   • Proving the base case
   • Proving the inductive step
   • Drawing a conclusion

   Hint

   It is what sets the stage for the entire induction.

4. 4.

   Is strong induction different from regular induction?

   • True
   • False

   Hint

   Think about how many cases can be assumed.

5. 5.

   Prove using induction that for all n >= 1, the sum of the first n integers is equal to n(n + 1)/2.

   Hint

   Think about how you can break down the sum at k + 1.

6. 6.

   Show that every integer greater than or equal to 40 can be represented as a sum of 4’s and 5’s using strong induction.

   Hint

   Focus on how the numbers can be formed by combining earlier proven cases.