A1 - Proof by induction | AQA A-Level Further Mathematics

Checking a formula for ten, a thousand or a million cases still leaves infinitely many cases unchecked. Proof by induction replaces that endless task with a starting case and a rule that carries truth to the next integer. You will use it to prove finite sums and recurrence formulae, and learn to recognise a gap in a proposed proof.

The structure of an induction proof

How can a finite argument prove infinitely many statements? The first few odd-number sums suggest

1=1^2,\qquad 1+3=2^2,\qquad 1+3+5=3^2

There is a reason the pattern continues: adding the next odd number, $2n+1$ , changes $n^2$ into $(n+1)^2$ . But this link needs a verified starting point.

Proof by induction

Let $P(n)$ be a statement about integers $n\ge n_0$ . A proof by induction establishes:

Basis: $P(n_0)$ is true.
Inductive step: for an arbitrary integer $k\ge n_0$ , assume $P(k)$ , then deduce $P(k+1)$ .
Conclusion: since the basis holds and truth passes from each integer to the next, $P(n)$ holds for every integer $n\ge n_0$ .

The assumption is called the induction hypothesis. You temporarily assume only the $k$ case in order to prove the implication $P(k)\Rightarrow P(k+1)$ ; you do not assume that both cases are true.

[DIAGRAM: asset_name: A starting case and a repeatable implication; asset_slug: aqa7367-induction-chain; caption: The basis starts the chain and the inductive implication extends it; description: A chain of boxes labelled P of one, P of two, P of three and P of four followed by dots. P of one has a checked basis label. Every arrow represents the same proved implication from P of k to P of k plus one. A second line states that the basis and the implication together give every positive integer case.]
The basis starts the chain and the inductive implication extends it

In proof notation, $p\Rightarrow q$ means “if $p$ , then $q$ ”; $p\Leftarrow q$ means “if $q$ , then $p$ ”. The symbol $p\Leftrightarrow q$ claims both directions. Induction needs the forward implication. You may also see $\therefore$ for “therefore” and $\because$ for “because”; words are equally clear.

Worked example 1: the sum of odd numbers

Question. Prove by induction that $\sum_{r=1}^{n}(2r-1)=n^2$ for all positive integers $n$ .

Plan. Verify the first sum and formula separately, then add the next odd number to the assumed sum.

For $n=1$ , the sum is $2\times1-1=1$ , and the formula is $1^2=1$ . The basis holds.

Assume, for an arbitrary integer $k\ge1$ ,

\sum_{r=1}^{k}(2r-1)=k^2

Then

\begin{aligned} \sum_{r=1}^{k+1}(2r-1) &=\sum_{r=1}^{k}(2r-1)+\bigl(2(k+1)-1\bigr) && \text{separate the new term}\\ &=k^2+2k+1 && \text{use the hypothesis}\\ &=(k+1)^2 && \text{factorise} \end{aligned}

Answer. The result holds for $n=1$ , and if it holds for $n=k$ , it holds for $n=k+1$ . Therefore, by induction, it holds for all positive integers $n$ .

Check. The new term is $2(k+1)-1=2k+1$ , not $2k-1$ . Independently, $(k+1)^2-k^2=2k+1$ , exactly the term added.

Now change every summand by adding $2$ : $2r-1$ becomes $2r+1$ . There are $n$ terms, so the proposed total changes from $n^2$ to $n^2+2n$ .

Worked example 2: shifting the odd numbers

Question. Prove by induction that $\sum_{r=1}^{n}(2r+1)=n(n+2)$ for all positive integers $n$ .

Plan. Keep the same proof structure, changing the added term and the target formula.

For $n=1$ , the sum is $3$ , and the formula is $1(1+2)=3$ .

Assume $\sum_{r=1}^{k}(2r+1)=k(k+2)$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} \sum_{r=1}^{k+1}(2r+1) &=k(k+2)+\bigl(2(k+1)+1\bigr) && \text{hypothesis plus new term}\\ &=k^2+4k+3 && \text{expand}\\ &=(k+1)(k+3) && \text{factorise}\\ &=(k+1)\bigl((k+1)+2\bigr) && \text{identify the next formula} \end{aligned}

Answer. The basis is true and $P(k)\Rightarrow P(k+1)$ . Hence, by induction, $\sum_{r=1}^{n}(2r+1)=n(n+2)$ for every positive integer $n$ .

Check. Finite-sum formulae independently give $2\sum r+\sum1=n(n+1)+n=n(n+2)$ .

The words in the conclusion describe the logical work you have done.

Watch out

“Assume true for $k$ , therefore true for $k+1$ ” skips the proof. Show where the hypothesis is used and reach the formula with every $n$ replaced by $k+1$ .

Try another constant shift of the same sum.

Proving recurrence formulae

A recurrence relation defines each term from earlier terms. Induction can prove a proposed explicit formula because the recurrence itself tells you how to move from term $u_k$ to the next.

For example, if $u_1=1$ and $u_{n+1}=2u_n+1$ , the first few terms are $1,3,7,15$ . These are each one less than a power of two, suggesting $u_n=2^n-1$ . The initial terms suggest the formula; the proof establishes it.

Worked example 3: a recurrence with a constant addition

Question. The sequence is defined by $u_1=1$ and $u_{n+1}=2u_n+1$ for integers $n\ge1$ . Prove that $u_n=2^n-1$ for all integers $n\ge1$ .

Plan. Check the initial term, then substitute the assumed explicit formula into the recurrence.

At $n=1$ , the recurrence's initial value is $u_1=1$ , and $2^1-1=1$ .

Assume $u_k=2^k-1$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} u_{k+1} &=2u_k+1 && \text{given recurrence}\\ &=2(2^k-1)+1 && \text{use the hypothesis}\\ &=2^{k+1}-1 && \text{simplify} \end{aligned}

Answer. The formula holds at $n=1$ , and its truth at $k$ implies its truth at $k+1$ . Thus $u_n=2^n-1$ for all integers $n\ge1$ , by induction.

Check. Add $1$ to both sides of the recurrence: $u_{n+1}+1=2(u_n+1)$ . Thus the shifted sequence doubles from $u_1+1=2$ , independently explaining the powers of two.

Change only the constant added in the recurrence, from $1$ to $3$ , while keeping $u_1=1$ . The explicit formula must change too.

Worked example 4: changing the recurrence constant

Question. Now $u_1=1$ and $u_{n+1}=2u_n+3$ for integers $n\ge1$ . Prove that $u_n=2^{n+1}-3$ for all integers $n\ge1$ .

Plan. Verify the same initial value, then use the changed recurrence in the inductive step.

At $n=1$ , the given term is $1$ , and $2^{1+1}-3=1$ .

Assume $u_k=2^{k+1}-3$ for an arbitrary integer $k\ge1$ . Then

\begin{aligned} u_{k+1} &=2u_k+3 && \text{given recurrence}\\ &=2(2^{k+1}-3)+3 && \text{use the hypothesis}\\ &=2^{k+2}-3 && \text{simplify}\\ &=2^{(k+1)+1}-3 && \text{the formula at }k+1 \end{aligned}

Answer. The basis and inductive implication hold. Therefore $u_n=2^{n+1}-3$ for every integer $n\ge1$ , by induction.

Check. The first terms from the recurrence are $1,5,13$ ; the formula gives the same. More structurally, $u_{n+1}+3=2(u_n+3)$ , so the shifted sequence doubles from $4$ .

In both examples, the given recurrence supplies a justified first line for $u_{k+1}$ . Starting with the formula you want for $u_{k+1}$ and merely rearranging it would not show that the defined sequence satisfies it.

Problem-solving

For a recurrence, write the definition of the next term first. Substitute the induction hypothesis only after that line, then compare with the explicit formula at $k+1$ .

Keep the initial value and change the constant again.

Why examples are not a proof

A numerical check can reveal an error, but even many successful checks do not establish a claim about every positive integer. There is always another integer beyond the last one checked.

For a concrete warning, consider the claim

n+(n-1)(n-2)(n-3)(n-4)=n \qquad\text{for every positive integer }n

At $n=1,2,3,4$ , one factor in the product is zero, so every check succeeds. At $n=5$ , the left side is $5+4\times3\times2\times1=29$ , while the right side is $5$ . The formula was designed to agree at the checked values, then fail.

Counterexample

A counterexample is one allowed case in which a universal claim is false. One counterexample disproves “for every”; a finite collection of successful examples does not prove it.

An induction argument avoids the gap because $k$ is arbitrary. Its algebra proves the implication for every allowed step, rather than checking just one transition such as $3$ to $4$ . With the basis, this reaches any positive integer after finitely many steps.

When checking a proposed proof, ask whether the basis was actually evaluated, whether only the current case was assumed, and whether the next case was deduced. The sentence “it is true for $k$ and for $k+1$ ” states two truths without explaining their dependence. The needed statement is “if it is true for $k$ , then it is true for $k+1$ ”.

Key idea

The basis supplies truth; the inductive step passes it on. Neither a collection of examples nor an implication without a starting case supplies both.

This answers the opening question: a finite proof can cover infinitely many integer cases because it proves a repeatable implication, not because it checks a very large sample.

Quick Recap

Verify the starting case on both sides of the proposed equality.
Assume the statement at an arbitrary allowed integer $k$ .
Use that hypothesis to deduce the statement at $k+1$ .
Conclude for the stated integer domain using both the basis and the implication.

Induction proves infinitely many cases through a starting point and a repeatable logical step.

Last Accessed

Core Pure

Mechanics

Statistics

Discrete Mathematics

A1 - Proof by induction

The structure of an induction proof

Proving recurrence formulae

Why examples are not a proof

Quick Recap

Learn faster with Nova