Proof by Induction and Strong Induction · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Climbing proofs by induction

Mathematics · Mathematical Thinking · ages 18-19
Name ______________________   Date ____________

  1. In a proof by induction that 1 + 2 + ... + n = n(n+1)/2, what is the base case?

    • Check n = 1, where both sides equal 1
    • Assume the formula holds for n = 1
    • Check n = 100 directly
    • Assume the formula holds for all n

  2. In a proof that 1 plus 2 up to n equals n times n plus 1 over 2, what is the base case?

    • Checking n equal to 100 directly
    • Checking n equal to 1, where both sides equal 1
    • Assuming the formula for all n

  3. Why does proving that every integer above 1 has a prime factor call for strong induction?

    • Weak induction only works for sums
    • The base case n equal to 2 fails
    • A composite n splits into factors far below n minus 1

  4. What does the inductive hypothesis assume in this sum proof?

    • The formula holds for some case k
    • The formula fails at k plus 1
    • That every integer is positive

  5. Mei assumes every integer from 2 up to k has a prime factor, then proves it for k plus 1. Mei is using strong induction.

    Circle one:   True   False

  6. Mei assumes every integer from 2 up to k has a prime factor, then proves it for k + 1. Is Mei using strong induction?

    Circle one:   True   False

  7. Assume 1 + 2 + ... + k = k(k+1)/2. What must the inductive step show for k + 1?

    • Adding k + 1 to both sides gives (k+1)(k+2)/2
    • The formula also holds for k + 2
    • The base case holds a second time
    • Every integer is positive

  8. Assume the sum up to k equals k times k plus 1 over 2. What must the step show for k plus 1?

    • That the base case holds a second time
    • Adding k plus 1 to both sides gives k plus 1 times k plus 2 over 2
    • That every integer above 1 is composite

  9. Take n equal to 12. The strong hypothesis covers every integer from 2 to 11. Which pair lets you finish the prime factor step?

    • 12 splits as 3 times 4, both covered by the range
    • 12 is prime so the base case fails
    • 12 needs weak induction instead

  10. Dan says an induction with a correct step but no base case still proves the claim.

    Circle one:   True   False

LightMySky · lightmysky.comW1-mt_7lvC02JBOC-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Climbing proofs by induction W1-mt_7lvC02JBOC-s1

  1. Check n = 1, where both sides equal 1 · The base case checks n = 1 directly: the sum is 1 and 1 times 2 divided by 2 is 1.
  2. Checking n equal to 1, where both sides equal 1 · The base case verifies the start directly: the sum is 1 and 1 times 2 over 2 is 1.
  3. A composite n splits into factors far below n minus 1 · Either factor can sit far below n minus 1, so assuming only the previous case says nothing about it.
  4. The formula holds for some case k · The hypothesis grants the k case so the step can use it to reach k plus 1.
  5. True · Using the whole earlier range instead of only case k is exactly strong induction.
  6. True · Mei is right to use strong induction: she assumes all earlier cases, not just the previous one.
  7. Adding k + 1 to both sides gives (k+1)(k+2)/2 · Add k + 1 to each side of the assumed formula and simplify to (k+1)(k+2)/2.
  8. Adding k plus 1 to both sides gives k plus 1 times k plus 2 over 2 · Add k plus 1 to each side and simplify to the formula with k plus 1 in place of k.
  9. 12 splits as 3 times 4, both covered by the range · Both factors sit inside the assumed range, so each brings its own prime factor.
  10. False · Skipping the anchor leaves the chain fastened to nothing, so Dan is wrong.
Worksheet · LightMySky