Fundamentals of Computing: Mathematical Induction for Computing Problems

Lesson overview

Prove claims about repeated structure.

CourseFundamentals of Computing

Topic strandProof

Assessment styleDigital exam practice

EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

Explain base case and inductive step.
Apply induction to a simple summation or algorithmic pattern.
Connect induction to loops and recursion.

Learning outcomes

By the end of this lesson, you can explain base case and inductive step.
By the end of this lesson, you can apply induction to a simple summation or algorithmic pattern.
By the end of this lesson, you can connect induction to loops and recursion.

Key vocabulary

What this lesson is about

Mathematical induction proves infinitely many statements by proving a starting case and a general step from one case to the next. It matches many computing structures such as loops, recursion and repeated processes.

Loop-invariant reasoning has the same shape: initialization is the base case, maintenance is the inductive step, and termination lets the preserved property prove something useful about the result.

A correct induction proof needs a base case, an inductive hypothesis and an inductive step. Leaving out any one of these weakens the argument.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

Mathematical inductionNamed proof technique. A method for proving statements about all natural numbers by proving a starting case and a general step from k to k+1.

Base caseInduction term. The first case proved directly, giving the induction chain a starting point.

Inductive hypothesisInduction term. The temporary assumption that the statement holds for an arbitrary case k.

Loop invariantComputing proof term. A property that is true before a loop starts, preserved by each iteration and useful when the loop finishes.

RecursionComputing term. A definition or algorithmic process that refers to a smaller instance of itself.

Formal notation and definitions

Base case: prove P(0) or P(1). Inductive step: assume P(k), then prove P(k + 1). Conclusion: therefore \foralln \geq n₀, P(n).

How to read the symbols

$P(n)$ A statement depending on the natural number n.

base caseThe first case proved directly.

inductive hypothesisAssume P(k) holds for an arbitrary k.

inductive stepUse P(k) to prove P(k+1).

Use the base case, inductive hypothesis and inductive step as separate parts of the argument. The proof fails if any part is missing.

Degree-level reasoning

A proof is a general argument over a whole domain, not a persuasive example. The domain and assumptions must be visible.

The strongest answers identify the structure of the claim first: universal, existential, implication, equality, recurrence or invariant.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

A loop invariant often has an induction shape: true before the loop, preserved by each iteration, useful when the loop finishes.

Objects: the statement P(n), the base case, the arbitrary case k, and the next case k + 1.

Model cue: Use a domino chain: the base case knocks over the first domino, and the inductive step proves each domino knocks over the next.

2. Mathematical working

P(n):\quad 1+2+\cdots+n=\frac{n(n+1)}{2}

P(1):\quad 1=\frac{1(2)}{2}

P(k)\Rightarrow P(k+1):\quad \frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}

\text{Loop invariant: initialise, preserve for one arbitrary iteration, use at termination}

Plain text version

Base case: prove P(0) or P(1).
Inductive step: assume P(k), then prove P(k + 1).
Conclusion: therefore ∀n ≥ n₀, P(n).

Worked use: For P(n): 1 + 2 + ... + n = n(n + 1)/2, the base case P(1) is 1 = 1. Assume P(k). Then 1 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, which is P(k + 1). Loop-invariant proofs use the same shape: true before the loop, preserved by an arbitrary iteration, useful at termination.

3. How to read the working

Read P(n) as the statement to be proved for every natural number n in the chosen range.
Check the base case directly, because the induction chain needs a first true statement.
In the inductive step, assume P(k) for an arbitrary k, then add k + 1 to both sides to reach P(k + 1).
Show the algebra that turns k(k + 1)/2 + (k + 1) into (k + 1)(k + 2)/2; this is the evidence for the general step.
Interpret the structure as repeated computation: a loop invariant holds initially, is preserved by each next iteration, and proves something at termination.

4. Computing meaning and check

Induction is a proof about repeated structure. The inductive step must show that an arbitrary valid stage forces the next one, which is why it matches loops and recursion.

Now check: Prove by induction that 1 + 2 + ... + n = n(n + 1)/2 for n ≥ 1, then name the matching base, maintenance and termination ideas in a loop invariant.

Worked example

From scenario to formal reasoning

Scenario: A loop invariant often has an induction shape: true before the loop, preserved by each iteration, useful when the loop finishes.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

For P(n): 1 + 2 + ... + n = n(n + 1)/2, the base case P(1) is 1 = 1. Assume P(k). Then 1 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, which is P(k + 1). Loop-invariant proofs use the same shape: true before the loop, preserved by an arbitrary iteration, useful at termination.

Worked solution structure

How a strong answer should be written

Define: State the domain and the objects under discussion. For this lesson, begin from Base case: prove P(0) or P(1).
Apply: Use the relevant definition from proof; do not rely on the diagram, wording or intuition alone.
Check: Test a boundary case, counterexample candidate or representation limit.
Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is proving only the next case from a specific example. Induction needs a general step from an arbitrary case to the next.

Guided practice

Prove the base case for 1 + 2 + ... + n = n(n + 1)/2 at n = 1.
Assume the formula for n = k and use it to prove the formula for k + 1.
Write the algebraic step that changes k(k + 1)/2 + (k + 1) into (k + 1)(k + 2)/2.
Describe how initialization and maintenance in a loop invariant match the base case and inductive step.

Quick checks

1. Which part starts an induction proof?

Base caseFinal diagramInductive hypothesis

2. The inductive step must prove:

P(1) implies P(2) onlyP(k) is falseP(k) implies P(k+1) for arbitrary k

Digital exam practice

Example exam task

Prove by induction that 1 + 2 + ... + n = n(n + 1)/2 for n ≥ 1, and describe how the same structure appears in loop-invariant reasoning.

Notation toolkit

P(n)

Means: the statement depending on n

How to use: Use it to name exactly what induction will prove.

P(1)

Means: a base case

How to use: Use it to start the induction chain.

P(k)\Rightarrow P(k+1)

Means: the inductive step

How to use: Use it to show the claim passes from one case to the next.

What a good answer is expected to show

A strong answer for this lesson defines the statement P(n), the base case, the arbitrary case k, and the next case k + 1, applies the proof method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

Read P(n) as the statement to be proved for every natural number n in the chosen range.
Check the base case directly, because the induction chain needs a first true statement.
In the inductive step, assume P(k) for an arbitrary k, then add k + 1 to both sides to reach P(k + 1).
Show the algebra that turns k(k + 1)/2 + (k + 1) into (k + 1)(k + 2)/2; this is the evidence for the general step.
Interpret the structure as repeated computation: a loop invariant holds initially, is preserved by each next iteration, and proves something at termination.

Model answer

Reveal model answer

P(n):\sum_{i=1}^{n}i=\frac{n(n+1)}{2}

P(1):1=\frac{1\cdot2}{2}

P(k)\Rightarrow P(k+1):\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}

Base case: for n = 1, 1 = 1(2)/2. Inductive hypothesis: assume 1 + ... + k = k(k + 1)/2. Then 1 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2, proving P(k + 1). Thus the formula holds for all n ≥ 1. This mirrors loop invariants: initialization, maintenance and termination.

Practise next

Prove the base case for 1 + 2 + ... + n = n(n + 1)/2 at n = 1.
Assume the formula for n = k and use it to prove the formula for k + 1.

Self-marking criteria

Proves the base case.
States the inductive hypothesis for arbitrary k.
Completes the algebra for k + 1.
Writes a valid conclusion for all n ≥ 1.
Links base/step to initialization/maintenance.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Graph Theory: Vertices, Edges, Paths and Cycles.