eduKate Singapore

VIEW THIS AS

Auto mode follows the Route Engine until you choose a viewpoint.

YOU ARE HERE

ROUTE CHECK

CONNECTED TO

WHAT NEXT

Use the canonical route for this room, or HELP if you are unsure.

Next useful routeCanonical hubHELP

Mathematics in Bukit Timah | Mathematical Induction, Recurrence and Proof by Patterns

—

by

eduKate Asia
Illustration of two students discussing mathematical reasoning with square tiles and a notebook.

A pupil spots a pattern: 1=1², 1+3=2², 1+3+5=3² and 1+3+5+7=4². The next few examples also work. Does that prove every sum of the first n positive odd numbers equals n²? The observations make a convincing conjecture, but checking a million examples still does not prove a statement for every positive integer. Mathematical induction provides the missing general argument.

This Mathematics in Bukit Timah guide builds a library of step-by-step proofs involving sums, powers, divisibility, inequalities and recursively defined sequences. Every story about paper tiles, classroom counters and mathematical learning sessions is fictional; nothing is presented as an actual Bukit Timah class record or student achievement. The emphasis is rigorous reasoning that can prepare interested learners for advanced Mathematics, not a claim that every proof here is required in G3 examinations.

The quick proof is this: suppose 1+3+⋯+(2k−1)=k². Add the next odd number 2k+1 to both sides. The new total is k²+2k+1=(k+1)². Because the identity is true for n=1 and a true case leads to the next true case, it holds for every positive integer n.

Article contents

Original illustrative lesson on examples and mathematical proof, used for invented square-counter sequences and induction rather than records of a real Bukit Timah school.

Quick answer: induction has a base case and a valid step

To prove a proposition P(n) for every integer n≥n₀, establish two things.

First, P(n₀) is true. Second, prove that for an arbitrary integer k≥n₀, if P(k) is true, then P(k+1) is true.

The second part is a conditional implication, not permission to claim P(k+1) without working. Together, the base and step cover the entire intended chain of integers.

Bukit Timah is the learning setting, not evidence of a particular result

A family near Beauty World, King Albert Park or Sixth Avenue may see children arranging counters, finding arithmetic patterns or preparing for advanced Mathematics.

But a statement about all integers is true or false independently of where it is studied. The diagrams and classroom examples below are deliberate mathematical constructions rather than local observation claims.

The purpose is to help learners distinguish a plausible pattern, a verified finite list and a valid proof covering infinitely many cases.

An observed pattern is a conjecture until justified

A conjecture is a statement proposed as true on the basis of observations or mathematical insight.

Checking n=1,2,3 and 4 for the odd-number sum makes the formula look credible. It does not yet establish that the same expression works for every n.

A rigorous proof must use a property that connects arbitrary cases. Induction does this through an implication that propagates truth from one integer to its successor.

Worked example 1: calculate the first four odd sums

The first odd number is one, and the sum is 1=1².

The first two give 1+3=4=2². The first three give 1+3+5=9=3². The first four give 1+3+5+7=16=4².

These are correct examples and a useful check on the proposed formula. They become a proof only when the general transition is also established.

The domino analogy explains the structure

Imagine infinitely many numbered dominoes standing in a line. Showing that the first domino falls is analogous to proving the base case.

Showing that any falling domino knocks down its immediate successor is analogous to the induction step. Together those conditions ensure every domino in the sequence falls.

The analogy is helpful, but the formal proof must show the mathematical base and implication. A picturesque story cannot replace the algebra.

The initial integer must be named

Some claims start at n=0, others at n=1 or n=5. The base case must use the first permitted integer in the proposition.

If a statement is true only for n≥5, proving it at n=1 may be impossible or irrelevant.

Students should read the quantifier and lower bound before applying an induction template. The domain is part of the theorem.

Worked example 2: a base case at zero

Consider 1+2+2²+⋯+2ⁿ=2ⁿ⁺¹−1, for integers n≥0.

At n=0, the left side has the single term one, while the right side is 2¹−1=1. The base is true.

Beginning at n=1 is not the stated first case. It might still allow a proof for n≥1, but it would omit n=0 unless separately checked.

A base case alone is not a general proof

Suppose P(1) is true, but no valid implication P(k)⇒P(k+1) has been proved. Nothing prevents P(2) from being false.

Likewise, a valid implication alone does not prove any specific instance without a starting true case from which it can propagate.

Induction needs both elements. An answer that merely substitutes n=1 and writes “therefore true for all n” is incomplete.

Worked example 3: a failed implication

Consider the false proposition P(n): n<3 for all positive integers.

P(1) is true and P(2) is true. But P(2)⇒P(3) fails, because 3<3 is false.

The induction chain breaks at the step. Checking two true examples cannot turn this universal statement into a theorem.

Prove the sum of first n natural numbers

The familiar formula is 1+2+⋯+n=n(n+1)/2 for every positive integer n.

The base at n=1 is 1=1(2)/2. Assume the formula holds for n=k.

Add the next term k+1 and simplify: k(k+1)/2+(k+1)=(k+1)[k/2+1]=(k+1)(k+2)/2. This is the formula with n replaced by k+1.

Worked example 4: label every induction line

Base: P(1) states 1=1, so true.

Hypothesis: Assume 1+2+⋯+k=k(k+1)/2 for some k≥1.

Step: Add k+1 to the assumed left side. The result simplifies to (k+1)(k+2)/2, which is exactly P(k+1). Therefore the identity holds for all positive integers by induction.

The final sentence follows only after the two preceding stages have been correctly completed.

The induction hypothesis is a temporary assumption

Inside the step, P(k) is assumed true for an arbitrary permitted k so that the implication can be proved.

That does not mean we are claiming P(k) has already been verified by substitution for every possible k. The base and step together establish the general theorem.

A common writing error is to say “assume P(k+1) is true” and then derive P(k+1). That is circular reasoning rather than induction.

A good step identifies the next term

When a formula concerns a sum up to n, the k+1 case usually consists of the k-case sum plus one new term.

For 1+2+⋯+n, the new term is k+1. For the first n odd numbers, the new term is 2k+1. For powers 1+2+⋯+2ⁿ, the new term is 2ᵏ⁺¹.

Choosing the wrong added term breaks the connection between P(k) and P(k+1).

Worked example 5: the odd-number sum

Let P(n) be 1+3+⋯+(2n−1)=n², n≥1.

Base n=1: 1=1². Assume P(k), meaning the first k odds sum to k².

The next odd is 2k+1. Add it to get k²+2k+1=(k+1)². Therefore P(k+1) holds, completing the induction.

A geometric square picture supports the algebra

Imagine arranging unit counters into an n-by-n square. To form a (n+1)-by-(n+1) square, add one row and one column, counting their common corner once.

The number of added counters is n+n+1=2n+1, the next odd number.

This visual construction explains why adding 2n+1 converts n² into (n+1)². It reinforces, rather than replaces, the symbolic induction step.

Worked example 6: extend a four-by-four square

A four-by-four square has sixteen counters. To make a five-by-five square, add a row of five and a column of four additional counters.

The added total is nine, the next odd number after seven. New total is 16+9=25=5².

The same structural calculation works with a general n, yielding n²+(2n+1)=(n+1)².

Induction can prove a geometric-series formula

Consider 1+2+2²+⋯+2ⁿ=2ⁿ⁺¹−1 for n≥0.

Base n=0 holds. Suppose the sum through 2ᵏ equals 2ᵏ⁺¹−1.

Add the next term 2ᵏ⁺¹ to obtain (2ᵏ⁺¹−1)+2ᵏ⁺¹=2×2ᵏ⁺¹−1=2ᵏ⁺²−1, which is the required n=k+1 expression.

Worked example 7: check the geometric sum at three

For n=3, the left side is 1+2+4+8=15.

The right side is 2⁴−1=16−1=15. The formula works.

This verifies one instance; the induction step shows why the same construction remains true beyond every checked example.

Divisibility statements suit induction

A statement such as “7ⁿ−1 is divisible by six for all n≥1” concerns a whole family of integers.

To prove divisibility, express the relevant quantity as a multiple of the divisor. A symbolic statement 7ᵏ−1=6m for some integer m gives the needed hypothesis.

The step should produce an expression of the same multiple form at k+1, rather than relying on calculator remainders from a few inputs.

Worked example 8: prove seven to n minus one is divisible by six

For n=1, 7−1=6, divisible by six.

Assume 7ᵏ−1 is a multiple of six, say 7ᵏ−1=6m. Then 7ᵏ⁺¹−1=7(7ᵏ−1)+6=7(6m)+6=6(7m+1).

Since 7m+1 is an integer, the new expression is divisible by six. Therefore the divisibility claim holds for every n≥1.

Why the added constant matters

The useful rewriting 7ᵏ⁺¹−1=7(7ᵏ−1)+6 keeps the assumed divisible expression visible.

Without that rearrangement, students sometimes write 7ᵏ⁺¹−1=7(7ᵏ−1), which is false: the right side equals 7ᵏ⁺¹−7.

A good induction step often involves adding and subtracting the same amount to expose the previous-case structure exactly.

Worked example 9: another divisibility formula

Prove 3²ⁿ−1 is divisible by eight for n≥1.

Base n=1: 3²−1=8. Suppose 3²ᵏ−1 is divisible by eight.

Then 3²⁽ᵏ⁺¹⁾−1=9×3²ᵏ−1=9(3²ᵏ−1)+8, a multiple of eight. The induction is complete.

Induction is not the only proof method

The claim that 7ⁿ−1 is divisible by six can also be shown using modular arithmetic because 7≡1 (mod 6), so 7ⁿ≡1 for positive integer n.

Different valid proofs illuminate different structures. Induction emphasises propagation from one case to the next; modular arithmetic emphasises remainder classes.

Students should not apply induction merely because a statement contains n. The chosen method should clarify the reasoning.

A recursive sequence supplies its own step

A recursively defined sequence gives a starting value and a rule for obtaining the next value from previous values.

For example, let a₁=2 and aₙ₊₁=aₙ+3. The terms are 2,5,8,11,…

A conjectured explicit formula is aₙ=3n−1. Induction verifies that the formula agrees with every term of the recurrence.

Worked example 10: prove a recurrence formula

Base n=1: 3(1)−1=2, matching a₁.

Assume aₖ=3k−1. By the recurrence, aₖ₊₁=aₖ+3=(3k−1)+3=3k+2=3(k+1)−1.

Therefore aₙ=3n−1 for every positive integer n. The proof uses the actual recurrence to connect consecutive terms.

Observing a finite sequence does not determine its future uniquely

The sequence 2,5,8,11 suggests adding three each time. Many different formulas can match these first four terms but produce another fifth term.

To prove a statement about all terms, an explicit rule or recurrence must be specified. Otherwise the pattern may be only a conjecture about an unspecified sequence.

Induction cannot make an arbitrary list’s future values known without a defining relationship.

Worked example 11: two rules with the same first four terms

Rule A is aₙ=3n−1, giving 2,5,8,11,14,…

Rule B is bₙ=3n−1+(n−1)(n−2)(n−3)(n−4). For n=1,2,3,4, the product is zero, so the first four terms match A.

At n=5, the added product is 4×3×2×1=24, so b₅=14+24=38. The first four observations alone do not choose between these valid rules.

Finite differences suggest but do not prove formulas

The squares 1,4,9,16,25 have first differences 3,5,7,9 and constant second differences two.

Such patterns suggest a quadratic formula in n. But a finite difference table does not establish that every unobserved term follows the same rule unless a defining assumption is supplied.

Induction can verify a proposed formula once the sequence has been specified appropriately.

Worked example 12: verify a square-number recurrence

Define a₁=1 and aₙ₊₁=aₙ+2n+1. Conjecture aₙ=n².

Base n=1: a₁=1. Assume aₖ=k². Then aₖ₊₁=k²+2k+1=(k+1)².

The formula is proved for all positive integers, now because the recurrence guarantees precisely which new term follows.

Induction can prove a formula for cubes

The sum of the first n positive cubes satisfies 1³+2³+⋯+n³=[n(n+1)/2]².

The right side is the square of the ordinary triangular-number sum. This identity can be verified for early n and proved generally by induction.

The algebraic step needs careful factorisation; skipping it can make a correct idea look like an unsupported jump.

Worked example 13: set up the cube-sum proof

Base n=1: 1³=1, and [1(2)/2]²=1.

Assume the sum through k³ equals [k(k+1)/2]². Add (k+1)³.

The new total is k²(k+1)²/4+(k+1)³. Factor (k+1)² to prepare for the next formula.

Worked example 14: complete the cube-sum algebra

Continue from (k+1)²[k²/4+(k+1)].

Inside the brackets, write [k²+4k+4]/4=(k+2)²/4. The new sum is (k+1)²(k+2)²/4.

This equals [((k+1)(k+2))/2]², exactly the formula with n=k+1. Therefore the cube-sum identity follows by induction.

Inequalities require careful direction preservation

Induction can prove inequalities such as 2ⁿ≥n+1 for every integer n≥0.

But after applying an induction hypothesis, the algebra must retain the correct inequality direction. Multiplication by a positive number preserves order; multiplying by a negative number reverses it.

A pupil who treats ≥ as ordinary equality can accidentally prove a false or unsupported statement.

Worked example 15: prove two to n is at least n plus one

Base n=0: 2⁰=1≥1.

Assume 2ᵏ≥k+1 for k≥0. Multiply both sides by positive two: 2ᵏ⁺¹≥2(k+1).

Since 2(k+1)≥k+2 for k≥0, we have 2ᵏ⁺¹≥k+2. Thus the induction step holds and the result is proved.

The comparison in an inequality step is essential

The previous proof did not end with 2ᵏ⁺¹≥2(k+1). The required target was k+2, so another comparison was needed.

An induction step must reach the exact desired P(k+1) statement, not merely a vaguely related bound.

Students should write the target before manipulating the hypothesis and ensure the final expression matches it.

Worked example 16: factorial versus powers of two

Prove n!≥2ⁿ⁻¹ for integers n≥1.

Base n=1: 1!=1 and 2⁰=1. Assume k!≥2ᵏ⁻¹.

Then (k+1)!=(k+1)k!≥(k+1)2ᵏ⁻¹≥2×2ᵏ⁻¹=2ᵏ because k+1≥2. This proves the next case.

The lower bound can change which base works

Consider the claim 2ⁿ>n² for all integers n≥5.

It holds at n=5 because 32>25. It is false at n=3, since 8<9, and it is not strict at n=4, since 16=16.

Choosing the starting value is not merely a formality. The truth of the universal statement depends on the specified domain.

Worked example 17: prove two to n exceeds n squared for n at least five

Base n=5: 2⁵=32>25.

Assume 2ᵏ>k² for k≥5. Then 2ᵏ⁺¹=2×2ᵏ>2k².

For k≥5, 2k²>(k+1)² because 2k²−(k+1)²=k²−2k−1>0. Hence 2ᵏ⁺¹>(k+1)², proving the statement.

Every inequality proof needs a permitted parameter range

The comparison 2k²>(k+1)² is not true for all real k or all small positive integers.

In the induction it is used only for k≥5, where it is valid. Stating that condition closes the logical gap.

A mathematician does not merely show that one expression is “obviously larger” without identifying when the comparison is justified.

Telescoping sums offer another induction exercise

Consider 1/(1×2)+1/(2×3)+⋯+1/[n(n+1)]=n/(n+1) for positive integers n.

Each summand can be rewritten as 1/j−1/(j+1), which makes adjacent terms cancel in the total.

This formula can be proved by telescoping or induction. Seeing both methods shows how a general expression can be explained through different mathematical structures.

Worked example 18: prove the telescoping identity by induction

Base n=1: 1/2=1/(1+1).

Assume the sum through k is k/(k+1). Add 1/[(k+1)(k+2)].

The new value is [k(k+2)+1]/[(k+1)(k+2)]=(k+1)²/[(k+1)(k+2)]=(k+1)/(k+2), the required next-case formula.

Why a denominator restriction belongs in the proof

The telescoping formula is stated for positive integers n, so j and j+1 in every denominator are nonzero.

If someone extends the formula blindly to negative or non-integer indices, the summation definition and denominators may no longer mean the same thing.

Formal statements should specify their indexing set. Induction is a method for discrete successor steps, not automatic proof for all real numbers.

An induction proof needs a clear P(n)

A strong written solution begins with “Let P(n) be the statement …” or an equivalent clear definition.

Without that sentence, the learner may lose track of what is being assumed and what exactly must be proved next.

The symbols P(k) and P(k+1) help separate an arbitrary known case from its successor, preventing circular wording.

Worked example 19: write P(k+1) before working

For P(n): 1+2+⋯+n=n(n+1)/2, write the target first: 1+2+⋯+k+(k+1)=(k+1)(k+2)/2.

Now the expression to be built is visible. Begin from the left and use the assumed k-case sum.

This planning step reduces the temptation to manipulate the target identity as though its truth were already established.

Starting with the target can conceal circular logic

Sometimes a student writes “to prove P(k+1)” and immediately replaces its left side with the right side, without showing why that equality follows from the hypothesis.

A proof should trace a valid chain of implications or equalities from known facts, not assume the desired statement as an unproved first step.

Working backwards is useful privately, but the final written proof must make the logic clear and noncircular.

A false theorem can have a convincing-looking induction argument

A famous fallacy claims all horses in a finite group have the same colour.

It attempts to reason that if every k-horse group is monochromatic, then any (k+1)-horse group can be covered by two overlapping k-horse groups, which supposedly forces the colours to match.

The flaw occurs at k=1: two one-horse groups inside a two-horse group have no horse in common, so the overlap argument does not connect their colours.

Worked example 20: locate the broken induction step

For two horses A and B, the two one-horse subsets are {A} and {B}.

Each subset trivially contains horses of one colour, but there is no shared horse whose colour can link A with B. The step P(1)⇒P(2) has not been proved.

The fallacy demonstrates that a valid base case plus a false induction-step argument does not establish the conclusion.

Strong induction uses all previous cases

Ordinary induction assumes P(k) and proves P(k+1). Strong induction may assume P(j) for every integer j from the starting case through k before proving P(k+1).

This is useful when the next object depends on smaller objects other than its immediate predecessor.

Strong induction is logically equivalent in proving ordinary integer-indexed results under suitable setup, but it often matches a recursive or factorisation argument more naturally.

Worked example 21: prime-factor existence by strong induction

Claim: every integer n≥2 is either prime or a product of primes.

Base n=2: two is prime. Assume every integer from 2 through k has the stated property.

For k+1, if it is prime, we are done. If composite, write k+1=ab with integers 2≤a,b≤k. By the strong hypothesis, both a and b are products of primes or primes, so their product is a product of primes.

Why ordinary one-step knowledge may be insufficient

A composite integer such as 12 can be written 3×4, and its factorisation relates to the smaller integers three and four, not simply eleven.

Strong induction permits using properties of all smaller integers needed in the construction.

The prime-factor existence proof shows why assuming only P(k) may be awkward even though the theorem itself is about consecutive integers.

Recurrences can depend on two previous terms

The Fibonacci-type recurrence F₁=1, F₂=1 and Fₙ₊₂=Fₙ₊₁+Fₙ uses two previous terms to determine the next.

A proof involving such sequences may require two base cases or a stronger induction hypothesis, depending on the claim.

Students must match the proof’s step to the recurrence’s dependencies. One starting value may not determine a second-order recurrence.

Worked example 22: define and check a Fibonacci identity

Let F₁=1,F₂=1 and Fₙ₊₂=Fₙ₊₁+Fₙ. The first values are 1,1,2,3,5,8,…

Conjecture F₁+F₂+⋯+Fₙ=Fₙ₊₂−1. At n=1, the left side is one and right side is F₃−1=2−1=1.

The base is true. The recurrence supplies the algebra needed to move from the k-case to the k+1-case.

Worked example 23: complete the Fibonacci sum proof

Assume F₁+⋯+Fₖ=Fₖ₊₂−1.

Add Fₖ₊₁. The new total becomes Fₖ₊₂+Fₖ₊₁−1.

By the Fibonacci recurrence, Fₖ₊₃=Fₖ₊₂+Fₖ₊₁. Thus the new sum is Fₖ₊₃−1, exactly the formula with n=k+1.

An induction statement must remain the same statement

Suppose a pupil proves that the sum of the first n odds equals n², then unexpectedly changes the claim to a sum of all integers.

Those are different propositions. The induction hypothesis must match the originally defined P(n) and the target P(k+1).

A good check is to substitute k+1 mechanically into the original formula and compare with the final induction-step expression.

Worked example 24: identify the correct next odd term

The kth positive odd number is 2k−1. The (k+1)th positive odd number is 2(k+1)−1=2k+1.

Thus the step adds 2k+1, not 2k−1 again and not 2k+2.

A one-term indexing error can spoil the entire proof even when the later algebra is neat.

A pattern in modular arithmetic can be proved by induction

Consider 6ⁿ−1 for positive integers n. Because 6≡1 modulo five, the expression should be divisible by five.

Induction establishes this without requiring large values of 6ⁿ.

Base n=1 gives five. The step exposes 6(6ᵏ−1)+5, which is a multiple of five whenever the earlier expression is.

Worked example 25: the five-divisibility proof

Assume 6ᵏ−1=5m for some integer m.

Then 6ᵏ⁺¹−1=6(6ᵏ−1)+5=6(5m)+5=5(6m+1).

Therefore the next case is divisible by five. Together with n=1, the induction proves the claim for all positive integers.

Induction can prove parity properties

Claim: n²−n is even for every integer n≥0.

The expression equals n(n−1), the product of two consecutive integers. One of them is even, giving a direct proof.

An induction proof is also possible, but the direct factor argument is simpler. This comparison reminds pupils to choose a clear method rather than mechanically use induction on every n-statement.

Worked example 26: an induction proof for evenness

Base n=0: 0²−0=0, even.

Assume k²−k is even. For k+1, calculate (k+1)²−(k+1)=k²+k.

Subtract the assumed expression k²−k to find difference 2k, an even integer. Thus the new expression is also even, proving the result.

Induction is not a licence to prove false claims

Before launching a proof, check small cases. A counterexample can reveal the proposed universal statement is false and save unnecessary effort.

For instance, the claim 2ⁿ>n² for every positive integer n fails at n=3 because 8<9.

No valid induction proof for the false statement exists. A failed base or step is a signal to revise the conjecture or domain, not to conceal the error.

Worked example 27: repair a false exponent claim

The claim 2ⁿ>n² is not true for all positive n, but it is true for n≥5.

Check base n=5: 32>25. Then the inequality step shown earlier proves the transition from k to k+1 for all k≥5.

Restricting the domain appropriately creates a valid theorem. It does not excuse claiming the stronger false statement.

What if the base holds only at a later integer?

Suppose P(n) is intended for n≥5. Proving P(5) and the step for all k≥5 establishes that range.

It does not establish P(1),P(2),P(3) or P(4). Those earlier values lie outside the claimed theorem.

The conclusion must match the starting point and the scope of the induction step exactly.

Worked example 28: a theorem starting at n equals two

Prove 3ⁿ≥2n+1 for integers n≥1. The base n=1 gives 3≥3.

Assume 3ᵏ≥2k+1. Then 3ᵏ⁺¹≥3(2k+1)=6k+3≥2k+3 for k≥0.

Thus the claim holds for n≥1. The proof would also work from a suitable earlier base if the statement and domain were revised consistently.

Beware of an unnecessary equality in inequality proofs

In the preceding step, 3(2k+1) and 2k+3 are generally not equal. The relationship needed is ≥, not equality.

Using an equality sign between unequal expressions is a real mathematical error, even if the final theorem happens to be true.

A careful proof keeps equality for exact algebra and inequalities for justified comparisons.

The statement P(k) can contain multiple terms

Some inductive assertions require proving two related identities together, or tracking an additional property that makes the step work.

Strengthening the induction hypothesis in this way can make a proof possible when a weaker claim does not provide enough information.

However, every strengthened statement also needs a base and valid step. Adding assumptions without proving them would change the problem improperly.

Worked example 29: prove two statements at once

Define a₁=1 and aₙ₊₁=2aₙ. Conjecture aₙ=2ⁿ⁻¹ and aₙ₊₁=2ⁿ.

These are closely related. The base a₁=1 matches 2⁰. Assuming aₖ=2ᵏ⁻¹, the recurrence gives aₖ₊₁=2ᵏ.

The next formula follows directly. If both were formally packaged into one stronger P(n), their relationships would need to be stated consistently at the same index.

Recursive definitions need complete initial data

For a sequence defined by aₙ₊₂=aₙ₊₁+aₙ, one initial value generally does not uniquely determine all later terms. Two starting values are needed.

For the simple first-order recurrence aₙ₊₁=aₙ+3, one starting value is enough.

Before proving a closed form, check whether the recurrence and initial conditions define a unique sequence under the intended domain.

Worked example 30: a missing initial condition

Suppose aₙ₊₂=aₙ₊₁+aₙ but only a₁=1 is given.

Choosing a₂=1 produces 1,1,2,3,… while choosing a₂=2 produces 1,2,3,5,…

Both satisfy the same recurrence and first value. Therefore the sequence is not uniquely defined until another initial value is provided.

A proof by induction is not always the best school-level response

If a Secondary pupil is asked to find the nth term of a simple arithmetic progression, the expected solution may be an arithmetic-pattern derivation rather than a formal induction proof.

Induction is especially useful when the task explicitly requires proving a formula for all integers or when the mathematics demands a general argument.

Avoid overstating assessment requirements. A rigorous extension can be valuable without being compulsory for the student’s present examination.

Mathematical induction and mathematical modelling differ

Induction proves a property of a precisely defined discrete mathematical system. A real dataset may show a pattern without having a recurrence that guarantees the future.

For instance, observing that a fictional class’s completed worksheet count increased by three across four sessions does not prove it will always do so.

The mathematical formula aₙ=3n−1 becomes provable only after the sequence is explicitly defined by a suitable rule. Evidence about actual learning behaviour requires separate observation and interpretation.

Why counterexamples and induction belong together

A counterexample disproves a universal claim by showing one permitted input where it fails.

Induction proves a true universal integer claim when its starting case and conditional step are both established. The methods serve opposite but complementary roles.

The Bukit Timah Counterexamples and Mathematical Claims guide covers the distinction between general proof and limited evidence. This article focuses on the specific successor-step proof technique.

A proof should have visible logical signposts

Write the claim P(n) clearly. State its domain. Then label the base case, induction hypothesis, induction step and conclusion.

The labels help the reader audit whether the conclusion follows. They also help a tutor identify whether the child’s first gap lies in choosing a base, using the assumed formula or completing the algebra.

A long calculation without these signposts can conceal that the required next case was never established.

Common error 1: check examples and say “therefore”

A student checks n=1,2,3 and concludes a conjecture holds for every positive integer.

Those checks are useful but finite. They do not cover infinitely many integers.

The correction is to require an arbitrary k and prove the implication P(k)⇒P(k+1), with a valid base. Only then is the induction conclusion justified.

Common error 2: assume the next case

A student begins “Assume P(k+1) is true” and later derives P(k+1).

The result is circular because the claim to be proved was used as a premise.

The standard induction hypothesis assumes P(k), or a properly stated set of prior cases for strong induction, and then proves the next assertion.

Common error 3: add the wrong next summand

For the first k odd numbers, the next odd is 2k+1. Adding 2k−1 again repeats the last term.

The repair is to write the nth term first and substitute n=k+1 to identify the successor term.

This index discipline also helps with geometric sums, recursive sequences and factorial comparisons.

Common error 4: do not reach the target form

A pupil arrives at k²+2k+1 and stops, claiming the step is complete.

That expression is correct, but the target P(k+1) is (k+1)². Factoring the trinomial makes the match explicit.

Induction steps should end with a clearly recognised version of the next-case proposition, not an unexplained intermediate expression.

Common error 5: use a step valid only outside its claimed domain

A student may use k²−2k−1>0 without checking the permitted k values.

The inequality holds for k≥3, but not for every nonnegative k. A proof using it must start in a domain where it is justified.

Writing parameter conditions is part of proving the step, not a footnote to add after the answer.

Common error 6: confuse recursion with observation

A pupil sees the numbers 2,5,8,11 and assumes all later terms add three.

A recurrence explicitly stating aₙ₊₁=aₙ+3 makes that progression definite; the finite list alone does not.

The correct question is whether the rule is given, proved, or only guessed from data.

Primary preparation: visual patterns and general reasoning

Younger learners can arrange square arrays of counters and notice that an n-by-n square grows by 2n+1 counters when extended.

They can explain a pattern geometrically without formal P(k) notation. This builds the habit of giving reasons rather than only filling in the next blank.

The purpose is conceptual progression; formal mathematical induction is not required merely to enjoy visual number patterns.

Secondary progression: algebra and sequence formulas

Learners should first be able to simplify algebraic expressions, factor quadratics, work with powers and understand nth-term notation.

Then an induction step becomes a meaningful extension: take a known expression at k, add the next term or apply the recurrence, and reach the expression at k+1.

If a student cannot expand (k+1)² or simplify fractions reliably, repair those foundations before assigning more complex proofs.

Junior College and advanced proof enrichment

Singapore’s SEAB 2027 A-Level syllabus directory provides course pathways, and the MOE H3 Mathematics syllabus resource lists mathematical induction among proof and reasoning methods.

The precise assessed requirements depend on whether a learner studies H1, H2, H3 or another pathway. This library article provides broad proof enrichment and is not a claim that induction is universally examinable in SEC G3 Mathematics.

The enduring skill is producing a valid general argument, not merely copying the format of a difficult-looking proof.

A twenty-minute family diagnostic

Minutes 1–5: Check the first three odd-number sums and ask why those examples are not a proof for all n.

Minutes 6–10: Define P(n): first n odds sum to n². Verify n=1 and assume P(k).

Minutes 11–15: Add the next odd 2k+1 and derive k²+2k+1=(k+1)². Ask why this proves P(k+1).

Minutes 16–20: Prove by induction that 7ⁿ−1 is divisible by six. Require the rewriting 7(7ᵏ−1)+6 and a complete base-case explanation.

A seven-day practice sequence

Day one distinguishes conjectures and theorems. Day two identifies starting cases. Day three practises the sum from one through n.

Day four proves the odd-number sum. Day five works with powers and geometric sums. Day six uses a divisibility statement. Day seven verifies a formula for a recursively defined sequence and explains why a finite number list alone is insufficient.

The learner should reproduce one proof from its key idea without copying a model paragraph. Independent reasoning is the meaningful test.

Practice questions with checked answers

A. What is the base for proving a statement for all n≥5? Answer: verify n=5.

B. What is the next odd number after 2k−1? Answer: 2k+1.

C. Simplify k²+2k+1. Answer: (k+1)².

D. If 1+⋯+k=k(k+1)/2, find the sum through k+1. Answer: (k+1)(k+2)/2.

E. Show 7ᵏ⁺¹−1 in terms of 7ᵏ−1. Answer: 7(7ᵏ−1)+6.

F. For a₁=2 and aₙ₊₁=aₙ+3, propose aₙ. Answer: 3n−1, provable by induction.

G. Does checking the first 1000 cases prove a universal integer statement? Answer: not by itself.

Frequently asked questions

What does mathematical induction prove?

It proves a proposition across a specified consecutive integer domain by establishing a starting case and a valid implication from each case to the next.

Why do I need a base case?

Without an established starting truth, the implication alone does not establish that any case is true.

Is the induction hypothesis circular reasoning?

No, when used correctly. It is a temporary assumption inside a conditional proof that P(k) implies P(k+1), not an assumption of the desired final conclusion.

Can induction start at n=0 or n=5?

Yes. The starting integer depends on the theorem’s stated domain, and the corresponding base must be verified.

Is checking many examples equivalent to induction?

No. Finitely many examples can support a conjecture but cannot generally prove it for every integer.

Why is the “all horses have one colour” argument wrong?

Its supposed overlap between consecutive subsets fails at the critical step from a one-object group to a two-object group.

When is strong induction useful?

When the next case depends on several smaller cases, such as a proof of prime-factor existence.

Can induction prove inequalities?

Yes, provided the base and step preserve valid inequality directions and the comparisons hold throughout the permitted domain.

Is induction the same as recursive definition?

No. Recursion defines a sequence; induction can prove general properties or explicit formulas of that sequence.

Is this compulsory for every Bukit Timah Secondary student?

No. It is advanced proof enrichment, with assessed scope depending on the student’s actual Mathematics pathway.

References and connected Bukit Timah Mathematics

For Singapore curriculum pathways, see the SEAB 2027 G3 Mathematics and Additional Mathematics syllabuses and SEAB 2027 A-Level syllabus directory. The MOE H3 Mathematics syllabus provides an official example of mathematical induction appearing in advanced proof education.

Continue with Mathematics in Bukit Timah | Counterexamples and Mathematical Proof, Arithmetic and Geometric Sequences, Prime Factorisation and Coprime Numbers and Modular Arithmetic for the arithmetic structures behind different induction examples.

The immutable Clementi Secondary 1 Mathematics tutoring reference anchors clear definitions, stage-by-stage reasoning, precise misconception diagnosis and independent checks.

The durable habit is to define the complete integer statement, prove its first permitted case, assume an arbitrary valid case only within a conditional step and derive the exact next statement without circular reasoning or hidden domain assumptions.

Read the three companion Mathematics in Bukit Timah lessons from this batch: Quadratic inequalities, sign charts and interval solutions · Indices, exponent laws and standard form · Sine rule, cosine rule and ambiguous triangles. They build foundations in algebraic signs, numerical representation, non-right triangle geometry and proof across discrete integer patterns, with original worked examples and independent checks.

Discover more from eduKate Singapore

Subscribe now to keep reading and get access to the full archive.

Continue reading