12.2.8. Example of Strong Induction

Try these first

1. 1.

   What is the base case for proving the statement that the sum of the first n integers is n(n + 1)/2?

   Hint

   Evaluate the formula when n equals the smallest integer.

2. 2.

   Explain what regular induction is.

   Hint

   Consider the two main steps involved in the process.

3. 3.

   What is the first step in proof by induction?

   • Proving the inductive step
   • Establishing the base case
   • Concluding the proof

   Hint

   Think about which step needs to be validated first.

4. 4.

   True or False: Strong induction only proves the existence of results for previous integers.

   • True
   • False

   Hint

   Consider the scope of what strong induction allows.

5. 5.

   Prove by induction that for all integers n ≥ 1, 2^n > n^2.

   Hint

   Consider properties of exponential growth versus polynomial growth.

6. 6.

   Demonstrate that every amount of postal charges greater than 11 can be paid using 3-rupee and 5-rupee coins.

   Hint

   Think about every integer in this case and how combinations transition logically.