Number

Step 8 of 18 · Worked example

← Number

0 of 3 done

Work through the example to CHECK to open the problems.

Reach CHECK to open the problems.Higher Level · Number · Step 8

Set out the base case, the induction hypothesis and the induction step separately.

Prove by induction, for all natural numbers n: (a) 1·2 + 2·3 + … + n(n + 1) = n(n + 1)(n + 2)/3; (b) 5²ⁿ − 1 is divisible by 24; (c) 3ⁿ > 2n.

Prove by induction that, for all natural numbers n:

(a) 1·2 + 2·3 + … + n(n + 1) = n(n + 1)(n + 2)/3

(b) 5²ⁿ − 1 is divisible by 24

(c) 3ⁿ > 2n

Read it once, slowly. Then copy it onto your page.
  • What is going on? Each statement must hold for all natural numbers n: 1, 2, 3, … with no end. A few checks can never be enough.
  • By induction fixes the method and the layout of every answer.
  • Three kinds of statement: (a) two sides are equal; (b) a number is a multiple of 24;
  • (c) one side is bigger than the other.
Céim

Higher Level Maths · Number · Step 8 of 18

Mathematical Induction & Number Proof

Base case, induction hypothesis and induction step, applied to identities, inequalities and divisibility patterns.

Why it matters

Induction is the standard Higher Level tool for proving that a statement holds for every natural number, and it is marked on the structure as much as the algebra.

The worked example

Prove by induction that, for all natural numbers n: (a) 1·2 + 2·3 + … + n(n + 1) = n(n + 1)(n + 2)/3 (b) 5²ⁿ − 1 is divisible by 24 (c) 3ⁿ > 2n

How the worked example goes

  1. Read

    • What is going on? Each statement must hold for all natural numbers n: 1, 2, 3, … with no end. A few checks can never be enough.
    • By induction fixes the method and the layout of every answer.
    • Three kinds of statement: (a) two sides are equal; (b) a number is a multiple of 24;
  2. Understand

    • (a) Is it even true?
    • n = 1: 1·2 = 2; (1·2·3)/(3) = 2
    • n = 2: 2 + 6 = 8; (2·3·4)/(3) = 8
  3. Reduce

    • (a) What do I write first?
    • n = 1: left 2, right 2 ✓
    • Assume: 1·2 + … + k(k + 1) = (k(k + 1)(k + 2))/(3)
  4. Solve

    • Start from the sum up to (k + 1)(k + 2). Which line comes next? (k(k + 1)(k + 2))/(3) + (k + 1)(k + 2): The assumption replaces the sum up to k(k + 1). Then add the next term, (k + 1)(k + 2).
    • (a) Take out the common factor.
    • (k(k + 1)(k + 2))/(3) + (k + 1)(k + 2)
  5. Check

    • (a) Is it right?
    • A new value, n = 4: 2 + 6 + 12 + 20 = 40 and (4·5·6)/(3) = 40 ✓
    • Base case, assumption used, closing sentence: all there ✓

Common mistakes to avoid

Key terms

proof by induction · base case · induction hypothesis · induction step · natural number · divisible · inequality