What must the final line of the inductive step show?

f(k+1)=d\times(an integer expression).

What are the two usual methods for the step?

Show f(k+1)-f(k) is a multiple of d, or substitute the hypothesis into f(k+1).

Why is k(k+1) always even?

One of two consecutive integers is even.

How do you obtain \mathbf{M}^{k+1} in an inductive proof?

\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}, with \mathbf{M}^k replaced by the assumed formula.

\mathbf{M}=\begin{pmatrix}1&1\\ 0&1\end{pmatrix}: what is \mathbf{M}^n?

\begin{pmatrix}1&n\\ 0&1\end{pmatrix}

\begin{pmatrix}2&0\\ 0&3\end{pmatrix}^n=?

\begin{pmatrix}2^n&0\\ 0&3^n\end{pmatrix}

Why calculate \mathbf{M}^2 and \mathbf{M}^3 before proving?

To spot the pattern or check the given formula for small n.

Write a full conclusion for a divisibility proof.

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

Induction for divisibility and matrix powersAQA A-Level Further Maths: Flashcards

Card 1 of 120 of 12 known

Question

How do you write the inductive hypothesis for divisibility by $d$?

Tap or press Space to reveal

Tap card or press Space to flip

See all 12 cards

How do you write the inductive hypothesis for divisibility by $d$ ?: $f(k)=dm$ for some integer $m$ .
What must the final line of the inductive step show?: $f(k+1)=d\times(\text{an integer expression})$ .
What are the two usual methods for the step?: Show $f(k+1)-f(k)$ is a multiple of $d$ , or substitute the hypothesis into $f(k+1)$ .
Simplify $5^{k+1}-5^k$ .: $4\times5^k$
Simplify $7^{k+1}-7^k$ .: $6\times7^k$
Why is $k(k+1)$ always even?: One of two consecutive integers is even.
Find $g(k+1)-g(k)$ for $g(n)=n^3+11n$ .: $3k^2+3k+12$
How do you obtain $\mathbf{M}^{k+1}$ in an inductive proof?: $\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}$ , with $\mathbf{M}^k$ replaced by the assumed formula.
$\mathbf{M}=\begin{pmatrix}1&1\\ 0&1\end{pmatrix}$ : what is $\mathbf{M}^n$ ?: $\begin{pmatrix}1&n\\ 0&1\end{pmatrix}$
$\begin{pmatrix}2&0\\ 0&3\end{pmatrix}^n=$ ?: $\begin{pmatrix}2^n&0\\ 0&3^n\end{pmatrix}$
Why calculate $\mathbf{M}^2$ and $\mathbf{M}^3$ before proving?: To spot the pattern or check the given formula for small $n$ .
Write a full conclusion for a divisibility proof.: True for $n=1$ ; if true for $n=k$ then true for $n=k+1$ ; so true for all positive integers $n$ by induction.

Exam questions on Induction for divisibility and matrix powers

Let $f(n)=5^n+3$ for positive integers $n$ . It is to be proved by induction that $f(n)$ is divisible by $4$ for all $n$ .
Assuming that $f(k)$ is divisible by $4$ , show that $f(k+1)$ is divisible by $4$ .2 marks
The matrix $\mathbf{M}=\begin{pmatrix}1&2\\ 0&1\end{pmatrix}$ satisfies $\mathbf{M}^n=\begin{pmatrix}1&2n\\ 0&1\end{pmatrix}$ for every positive integer $n$ .
Find the smallest positive integer $n$ for which the top-right entry of $\mathbf{M}^n$ is greater than $1000$ .2 marks
Let $\mathbf{A}=\begin{pmatrix}3&-2\\ 2&-1\end{pmatrix}$ . A student conjectures that $\mathbf{A}^n=\begin{pmatrix}1+2n&-2n\\ 2n&1-2n\end{pmatrix}$ for all positive integers $n$ .
Calculate $\mathbf{A}^2$ and $\mathbf{A}^3$ , and show that the conjecture is correct for $n=2$ and $n=3$ .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).