What is the basis step?

Show the statement is true for n=1, evaluating both sides.

What is the inductive hypothesis?

Assume the statement is true for n=k, for some positive integer k.

How do you reach u{k+1} in a recurrence proof?

Substitute the hypothesis for uk into the recurrence u{k+1}=f(uk).

Write a full conclusion.

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

Which common error occurs when adding the new term?

Adding the kth term again instead of the (k+1)th term f(k+1).

Induction for series and sequencesAQA A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

What are the four stages of a proof by induction?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

What are the four stages of a proof by induction?: Basis step, inductive hypothesis, inductive step, conclusion.
What is the basis step?: Show the statement is true for $n=1$ , evaluating both sides.
What is the inductive hypothesis?: Assume the statement is true for $n=k$ , for some positive integer $k$ .
Write $\sum_{r=1}^{k+1}f(r)$ using $\sum_{r=1}^{k}f(r)$ .: $\sum_{r=1}^{k}f(r)+f(k+1)$
What is $\sum_{r=1}^{n}r$ ?: $\frac{n(n+1)}{2}$
What is $\sum_{r=1}^{n}r^2$ ?: $\frac16n(n+1)(2n+1)$
What is $\sum_{r=1}^{n}r^3$ ?: $\frac14n^2(n+1)^2$
What is $\sum_{r=1}^{n}(2r-1)$ ?: $n^2$
Simplify $\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}$ .: $\frac{k+1}{k+2}$
How do you reach $u_{k+1}$ in a recurrence proof?: Substitute the hypothesis for $u_k$ into the recurrence $u_{k+1}=f(u_k)$ .
Write a full conclusion.: True for $n=1$ ; if true for $n=k$ then true for $n=k+1$ ; so true for all positive integers $n$ by induction.
Which common error occurs when adding the new term?: Adding the $k$ th term again instead of the $(k+1)$ th term $f(k+1)$ .

Exam questions on Induction for series and sequences

Let $S_n=\sum_{r=1}^{n}r(r+1)$ for positive integers $n$ . A student is proving by induction that $S_n=\frac{n(n+1)(n+2)}{3}$ .
Show that $\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)=\frac{(k+1)(k+2)(k+3)}{3}$ .2 marks
For positive integers $n$ , let $T_n=\sum_{r=1}^{n}\frac{1}{r(r+1)}$ . It is to be proved by induction that $T_n=\frac{n}{n+1}$ .
Write down the basis step for $n=1$ and state the inductive hypothesis.2 marks
The sequence $u_n$ is defined by $u_1=3$ and $u_{n+1}=3u_n-2$ for $n\ge1$ . A student suggests that $u_n=2\times3^{n-1}+1$ .
Find $u_2$ , $u_3$ and $u_4$ , and show that the suggested formula gives the correct value of $u_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).