What do you assume in the inductive step?

That the statement is true for n=k.

What must you prove in the inductive step?

That the statement is true for n=k+1.

Write a full conclusion for an induction proof.

True for n=1, and if true for n=k then true for n=k+1, so true for all positive integers n by mathematical induction.

First move in the inductive step for \sum{r=1}^{n}f(r)?

\sum{r=1}^{k+1}f(r)=\sum{r=1}^{k}f(r)+f(k+1), then substitute the assumed formula.

How do you prove f(n) is divisible by m?

Show f(1) is divisible by m, then show f(k+1)-a\,f(k) (or f(k+1) in terms of f(k)) is a multiple of m.

How do you prove a formula for un given u{n+1}=g(un)?

Check n=1, assume uk equals the formula, and substitute it into u{k+1}=g(uk).

How do you prove a formula for \mathbf{A}^n?

Show n=1, assume for n=k, then multiply \mathbf{A}^{k+1}=\mathbf{A}^k\mathbf{A}.

Why is the basis case essential?

It starts the chain; without it the step proves nothing about any actual case.

Why is the inductive step essential?

It links each case to the next, so the truth of n=1 passes to every n.

Where do you write the target of the proof?

At the start of the step, as P(k+1) with n replaced by k+1, so you know what to reach.

Proof by mathematical inductionEdexcel International A Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

What are the four parts of an induction proof?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

What are the four parts of an induction proof?: Basis ( $n=1$ ), assumption ( $n=k$ ), inductive step ( $n=k+1$ ) and conclusion.
What do you assume in the inductive step?: That the statement is true for $n=k$ .
What must you prove in the inductive step?: That the statement is true for $n=k+1$ .
Write a full conclusion for an induction proof.: True for $n=1$ , and if true for $n=k$ then true for $n=k+1$ , so true for all positive integers $n$ by mathematical induction.
First move in the inductive step for $\sum_{r=1}^{n}f(r)$ ?: $\sum_{r=1}^{k+1}f(r)=\sum_{r=1}^{k}f(r)+f(k+1)$ , then substitute the assumed formula.
How do you prove $f(n)$ is divisible by $m$ ?: Show $f(1)$ is divisible by $m$ , then show $f(k+1)-a\,f(k)$ (or $f(k+1)$ in terms of $f(k)$ ) is a multiple of $m$ .
For $f(n)=7^n-1$ , what is $f(k+1)$ in terms of $f(k)$ ?: $f(k+1)=7f(k)+6$
How do you prove a formula for $u_n$ given $u_{n+1}=g(u_n)$ ?: Check $n=1$ , assume $u_k$ equals the formula, and substitute it into $u_{k+1}=g(u_k)$ .
How do you prove a formula for $\mathbf{A}^n$ ?: Show $n=1$ , assume for $n=k$ , then multiply $\mathbf{A}^{k+1}=\mathbf{A}^k\mathbf{A}$ .
Why is the basis case essential?: It starts the chain; without it the step proves nothing about any actual case.
Why is the inductive step essential?: It links each case to the next, so the truth of $n=1$ passes to every $n$ .
Where do you write the target of the proof?: At the start of the step, as $P(k+1)$ with $n$ replaced by $k+1$ , so you know what to reach.

Exam questions on Proof by mathematical induction

A student is proving by induction that $\sum_{r=1}^{n}r=\frac{n(n+1)}{2}$ for all positive integers $n$ , and has already checked the case $n=1$ .
Assuming the result is true for $n=k$ , show that it is true for $n=k+1$ .2 marks
Let $f(n)=7^n-1$ for positive integers $n$ .
Hence, or otherwise, show that if $f(k)$ is divisible by $6$ then $f(k+1)$ is divisible by $6$ .2 marks
A sequence is defined by $u_1=2$ and $u_{n+1}=2u_n+3$ for $n\ge1$ .
Find $u_2$ , $u_3$ and $u_4$ , and verify that the formula $u_n=5\times2^{n-1}-3$ gives the correct values for $n=1,2,3,4$ .3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).