Inductive step for a sum \sum{r=1}^{n}ur?

Add the (k+1)th term u{k+1} to the assumed sum, then factorise.

Write a full induction conclusion.

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

Base case for \sum{r=1}^{n}r^3=\frac14n^2(n+1)^2?

n=1: LHS =1, RHS =\frac14\times1\times4=1.

Add and factorise: \frac14k^2(k+1)^2+(k+1)^3?

\frac14(k+1)^2\left[k^2+4(k+1)\right]=\frac14(k+1)^2(k+2)^2

How do you show f(k+1) is divisible by d?

Write f(k+1)-a\,f(k) as a multiple of d, or substitute the assumed form and factor out d.

f(n)=3^{2n}+11: find f(k+1)-f(k).

3^{2k+2}-3^{2k}=8\times3^{2k}, a multiple of 4.

How do you set up the inductive step for \mathbf{M}^n?

Assume \mathbf{M}^k equals the formula, then calculate \mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}.

Why must the basis case be shown?

Without a first true statement, the chain P(k)\Rightarrow P(k+1) has nothing to start from.

What must you check in a matrix inductive step?

All four entries equal the formula with n replaced by k+1.

Common mistake in the inductive step?

Assuming P(k+1) at the start instead of deriving it from P(k).

Proof by mathematical inductionEdexcel 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 case, assumption for $n=k$ , inductive step to $n=k+1$ , conclusion.
Inductive step for a sum $\sum_{r=1}^{n}u_r$ ?: Add the $(k+1)$ th term $u_{k+1}$ to the assumed sum, then factorise.
Write a full induction conclusion.: True for $n=1$ , and if true for $n=k$ then true for $n=k+1$ , so true for all positive integers $n$ by induction.
Base case for $\sum_{r=1}^{n}r^3=\frac14n^2(n+1)^2$ ?: $n=1$ : LHS $=1$ , RHS $=\frac14\times1\times4=1$ .
Add and factorise: $\frac14k^2(k+1)^2+(k+1)^3$ ?: $\frac14(k+1)^2\left[k^2+4(k+1)\right]=\frac14(k+1)^2(k+2)^2$
How do you show $\mathrm{f}(k+1)$ is divisible by $d$ ?: Write $\mathrm{f}(k+1)-a\,\mathrm{f}(k)$ as a multiple of $d$ , or substitute the assumed form and factor out $d$ .
$\mathrm{f}(n)=3^{2n}+11$ : find $\mathrm{f}(k+1)-\mathrm{f}(k)$ .: $3^{2k+2}-3^{2k}=8\times3^{2k}$ , a multiple of 4.
If $7^k=6m-5$ , write $7^{k+1}+5$ as a multiple of 6.: $7(6m-5)+5=42m-30=6(7m-5)$
How do you set up the inductive step for $\mathbf{M}^n$ ?: Assume $\mathbf{M}^k$ equals the formula, then calculate $\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}$ .
Why must the basis case be shown?: Without a first true statement, the chain $P(k)\Rightarrow P(k+1)$ has nothing to start from.
What must you check in a matrix inductive step?: All four entries equal the formula with $n$ replaced by $k+1$ .
Common mistake in the inductive step?: Assuming $P(k+1)$ at the start instead of deriving it from $P(k)$ .

Exam questions on Proof by mathematical induction

Proof by mathematical induction is used to show that $\sum_{r=1}^{n}\frac{1}{r(r+1)}=\frac{n}{n+1}$ for all positive integers $n$ .
Show that if the result is true for $n=k$ then it is true for $n=k+1$ .2 marks
Let $\mathrm{f}(n)=7^n+5$ , where $n$ is a positive integer.
Given that $\mathrm{f}(k)$ is divisible by 6 for some positive integer $k$ , show that $\mathrm{f}(k+1)$ is also divisible by 6.2 marks
The matrix $\mathbf{A}=\begin{pmatrix}2&1\\0&1\end{pmatrix}$ .
Find $\mathbf{A}^2$ and $\mathbf{A}^3$ , and hence suggest a formula for $\mathbf{A}^n$ .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).