HSC Study

Further Mathematical Induction

Induction with base cases above 1 and steps of 2, sums in sigma notation, inequalities such as 2ⁿ > n², divisibility results, and proving formulas for first-order recursive sequences.

60 min · Proof

Assumes you have read Proof by Mathematical Induction and Proving Inequalities.

The full teaching. Start here.

The short version

  1. Base case: check the smallest in the set, such as for "", or for "even ".
  2. Hypothesis: assume the result for some in the set. Write it as an equation (for example ) or as an inequality.
  3. Step: prove it for the next member: , or for even or odd . Use the hypothesis explicitly.
  4. Conclusion: "by mathematical induction, true for all …".
  • Sums: .
  • Inequalities: after using the hypothesis, prove a separate small inequality to reach the form.
  • Recursions: substitute the hypothesis into .

Adjusting the base case and the step

Induction works like dominoes. The base case knocks over the first domino, and the step shows each domino knocks over the next. Both must match the set of in the claim:

  • "for all ": base , step ;
  • "for all even ": base , step ;
  • "for all odd ": base , step .

Worked example3 marks

Induction over even numbers

Prove that is a multiple of for every even positive integer .

Base case

Smallest even positive integer.

: , a multiple of .

Hypothesis

Some even k.

Assume for some even and integer .

Step to k + 2

The next even number.

. Since is even, for an integer , so the total is .

Answer

True for , and true for implies true for . By induction, true for all even positive integers.

Is that answer sensible?

: . : . The claim fails for odd ( gives ), which is why stepping by is essential.

CheckpointAnswer before reading on.

To prove a statement for all even positive integers n by induction, which structure is correct?

Select one answer

Hint 1Smallest even positive integer.

Hint 2Next even number after k.

Hint 3k to k + 2.

CheckpointAnswer before reading on.

To prove for all integers , what is the base case?

Select one answer

Hint 1Smallest n in the set.

Hint 2n > 4.

Hint 3n = 5.

Exam question

Standard · about 5 min

3 marks

Prove by induction that is divisible by for all odd positive integers .

Hint 1Base n = 1.

Hint 2Step k to k + 2.

Hint 3.

Where students lose marks on this one
  • Stepping to k + 1.

    Why it happens: Wrong step size.

    Odd numbers go up by 2.

Written for this site.

Sigma notation

means . The letter is a dummy index, and is the upper limit. The key identity for induction is

so the step always adds exactly one new term.

Worked example3 marks

A sum in sigma notation

Prove that for all positive integers .

Base case

N = 1.

LHS and RHS .

Add the next term

Assume true for N = k.

.

Factorise

Aim for (k + 1)/(2k + 3).

, so the sum is .

Answer

By induction, the formula holds for all positive integers .

Is that answer sensible?

: , and matches.

CheckpointAnswer before reading on.

Evaluate .

Hint 1Substitute r = 1, 2, 3, 4.

Hint 21 + 4 + 9 + 16.

Hint 330.

CheckpointAnswer before reading on.

Which is in sigma notation?

Select one answer

Hint 1General term.

Hint 2r-th term r(r + 1).

Hint 3r from 1 to n.

Exam question

Standard · about 5 min

3 marks

Prove by induction that for all positive integers .

Hint 1Base n = 1: 2 = 2.

Hint 2Add (k + 1)(k + 2).

Hint 3Factor (k + 1)(k + 2).

Where students lose marks on this one
  • Expanding everything into a cubic.

    Why it happens: Making algebra harder.

    Factor out (k + 1)(k + 2) first.

Written for this site.

Exam question

Standard · about 5 min

3 marks

Prove by induction that for all positive integers .

Hint 1Base: 1/2.

Hint 2Add .

Hint 3Numerator .

Where students lose marks on this one
  • Adding 1/(k(k + 1)) as the new term.

    Why it happens: Wrong next term.

    Replace r by k + 1.

Written for this site.

Exam question

Standard · about 5 min

3 marks

Prove by induction that .

Hint 1Base: 1 = 1.

Hint 2Factor .

Hint 3.

Where students lose marks on this one
  • Expanding to degree 4.

    Why it happens: Messy algebra.

    Factor (k + 1)² first.

Written for this site.

Exam question

Harder · about 5 min

3 marks

Prove by induction that for all positive integers .

Hint 1Base: 2 = 0 + 2.

Hint 2Add .

Hint 3.

Where students lose marks on this one
  • Writing 2k·2^(k + 1) = k·2^(2k + 2).

    Why it happens: Index law error.

    2 × 2^(k + 1) = 2^(k + 2).

Written for this site.

Exam question

Standard · about 5 min

3 marks

Prove by induction that .

Hint 1Base: 1 = 2 − 1.

Hint 2Add .

Hint 3.

Where students lose marks on this one
  • Writing (k + 1)(k + 1)! = (k + 2)!.

    Why it happens: Factorial error.

    (k + 2)! = (k + 2)(k + 1)!.

Written for this site.

Inequalities

Inequality steps rarely land exactly on the target. Typically you use the hypothesis to get , and then prove separately that .

Worked example4 marks

An inequality by induction

Prove that for all integers .

Base case

The smallest integer greater than 4.

: .

Use the hypothesis

Assume 2ᵏ > k² for some k ≥ 5.

.

Bridge to (k + 1)²

Show 2k² ≥ (k + 1)².

for .

Combine

Chain the two inequalities.

.

Answer

By induction, for all integers .

Is that answer sensible?

The bridge needs , true for , but the base case at fails (). So both parts are needed, and the result really does start at .

CheckpointAnswer before reading on.

In proving for integers , what is the correct inductive hypothesis?

Select one answer

Hint 1Assume for some k in the set.

Hint 2Not for all k.

Hint 3k ≥ 5.

Exam question

Standard · about 5 min

3 marks

Prove by induction that for all integers .

Hint 1Base: 24 > 16.

Hint 2.

Hint 3.

Where students lose marks on this one
  • Base case n = 1.

    Why it happens: The claim is false for n = 1, 2, 3.

    Start where the statement begins.

Written for this site.

Exam question

Harder · about 5 min

3 marks

Prove by induction that for all positive integers and all real .

Hint 1Base n = 1: equality.

Hint 2Multiply by 1 + x > 0.

Hint 3Drop .

Where students lose marks on this one
  • Multiplying by (1 + x) without noting 1 + x > 0.

    Why it happens: Missing the condition.

    That is exactly why x > −1 is needed.

Written for this site.

Exam question

Harder · about 6 min

4 marks

Prove by induction that for all integers .

Hint 1Base: 81 > 64.

Hint 2.

Hint 3For : , .

Where students lose marks on this one
  • Stopping at 3^(k + 1) > 3k³ without comparing to (k + 1)³.

    Why it happens: Incomplete step.

    You must reach (k + 1)³.

Written for this site.

Exam question

Harder · about 6 min

4 marks

Prove by induction that for all positive integers .

Hint 1Base: 1 ≤ 1.

Hint 2Need .

Hint 3Reduces to .

Where students lose marks on this one
  • Starting from the required inequality and "proving" it.

    Why it happens: Working backwards without reversibility.

    Show the needed inequality holds, with reversible steps.

Written for this site.

Divisibility

Write the hypothesis as an equation, such as , and rewrite in terms of .

Worked example3 marks

A divisibility proof

Prove that is divisible by for all positive integers .

Base case

n = 1.

.

Hypothesis as an equation

Makes substitution possible.

Assume , so .

Step

n = k + 1.

.

Answer

Divisible by for , so by induction for all positive integers .

Is that answer sensible?

: .

CheckpointAnswer before reading on.

In proving by induction, how is the inductive hypothesis best written?

Select one answer

Hint 1Divisible means equals 7 × integer.

Hint 2Introduce M.

Hint 3.

Exam question

Standard · about 4 min

3 marks

Prove by induction that is divisible by for all positive integers .

Hint 1Base: 7.

Hint 2.

Hint 3.

Where students lose marks on this one
  • Writing 2^(3k + 3) = 2^(3k) + 8.

    Why it happens: Index law error.

    2^(3k + 3) = 2^(3k) × 2³.

Written for this site.

Exam question

Standard · about 5 min

3 marks

Prove by induction that is divisible by for all positive integers .

Hint 1Base: 27.

Hint 2.

Hint 3.

Where students lose marks on this one
  • Not splitting off the hypothesis.

    Why it happens: Not using the assumption.

    Rewrite to include 5^k + 2·11^k.

Written for this site.

Recursive formulae

A first-order recursion gives each term from the one before, as in with . Induction proves a closed formula: check the first term, then substitute the hypothesis for into the recursion.

Worked example3 marks

Proving a formula for a recursion

A sequence has and . Prove that for all .

Base case

First term.

.

Step

Assume a_k = 2ᵏ − 1 and use the recursion.

.

Answer

By induction, for all .

Is that answer sensible?

Terms from the recursion: . The formula gives .

CheckpointAnswer before reading on.

A sequence has and . Find .

Hint 1Generate terms.

Hint 21, 3, 7, …

Hint 315.

Exam question

Standard · about 4 min

3 marks

A sequence has and . Prove by induction that .

Hint 1Base: 3⁰ + 1 = 2.

Hint 2Substitute the hypothesis into the recursion.

Hint 3.

Where students lose marks on this one
  • Checking the first few terms only.

    Why it happens: Using examples.

    Induction proves it for all n.

Written for this site.

Exam question

Standard · about 4 min

3 marks

A sequence has and . Prove by induction that .

Hint 1Base: a₁ = 1.

Hint 2.

Hint 3Multiply top and bottom by k.

Where students lose marks on this one
  • Writing (1/k)/(1 + 1/k) = 1/(1 + k²).

    Why it happens: Fraction error.

    Multiply numerator and denominator by k.

Written for this site.

Why both parts matter

CheckpointAnswer before reading on.

A student "proves" that is even for all positive integers : if is even, then is even. What is wrong?

Select one answer

Hint 1Check n = 1.

Hint 23 is odd.

Hint 3The base case fails.

CheckpointAnswer before reading on.

"All horses are the same colour": for n horses, remove one to get n − 1 of the same colour, remove another to get another n − 1 of the same colour, and the overlap forces all n to match. Where does this fail?

Select one answer

Hint 1Try n = 2.

Hint 2Overlap size n − 2.

Hint 3Zero overlap.

Common mistake

Assume 2ᵏ > k². Then 2ᵏ⁺¹ > (k + 1)². Check: 2·2ᵏ > k² + 2k + 1, which is true because 2ᵏ > k².

Why it happens: This writes down the goal and then asserts it, rather than deriving it.

Start from the left side, , apply the hypothesis to get , and then prove the bridge with the condition . Every inequality sign in the chain needs a reason.

What lifts this to a Band 6

In the step, write "RTP:" (required to prove) followed by the exact statement for before you start. Then write your working as one chain starting from the left side, and mark where the hypothesis is used ("by the inductive hypothesis"). Markers look for that explicit use of the hypothesis, and the RTP line stops you aiming at the wrong target.

Strong induction

Some recursions depend on two earlier terms, such as the Fibonacci sequence . Proving needs two base cases ( and ) and a hypothesis covering both and : then . This is strong induction: you may assume the result for every value up to . It is no more powerful logically, but it is often more convenient.