Edexcel A-Level Mathematics AS Fp1 8 Proof Questions

Practise induction proofs for series, divisibility, matrices and sequences, with clear base cases and algebraic k to k + 1 steps.

Exam points

set up the base case and induction hypothesis for sums, matrices or recurrence formulae
transform the k + 1 case to use the assumed result and complete a divisibility or identity proof

Covered syllabus points

FP1.8.1 - Proof by mathematical induction

[Maximum number: 10]

(a)

Prove by induction that for $n \in \mathbb{Z}^{+}$

\left(\begin{array}{rr} 5 & -1 \\ 4 & 1 \end{array}\right)^{n}=3^{n-1}\left(\begin{array}{cc} 2 n+3 & -n \\ 4 n & 3-2 n \end{array}\right)

[ 5 ]

Let
$A=\left(\text{row }1:5,\ -1;\ \text{row }2:4,\ 1\right).$
For n=1, the right-hand side gives A. B1

Assume true for n=k:
$A^k=3^{k-1}\left(\text{row }1:2k+3,\ -k;\ \text{row }2:4k,\ 3-2k\right).$
Then
$A^{k+1}=3^{k-1} \left(\text{row }1:2k+3,\ -k;\ \text{row }2:4k,\ 3-2k\right)A.$ $=3^{k-1}\left(\text{row }1:6k+15,\ -3k-3;\ \text{row }2:12k+12,\ -6k+3\right).$ $=3^k\left(\text{row }1:2(k+1)+3,\ -(k+1);\ \text{row }2:4(k+1),\ 3-2(k+1)\right).$
Thus true for n=k+1. Since true for n=1, the result is true for all $n\in\mathbb Z^+$ . A1cso

(b)

Prove by induction that for $n \in \mathbb{Z}^{+}$

f(n)=8^{2 n+1}+6^{2 n-1}

is divisible by 7

[ 5 ]

$\mathrm{f}(1)=8^{3}+6=518=74 \times 7$ (so true for n=1 )
Assume true for n=k so that $8^{2 k+1}+6^{2 k-1}$ is divisible by 7

$\mathrm{f}(k+1)=8^{2 k+3}+6^{2 k+1}$ $=64 \times\left(8^{2 k+1}+6^{2 k-1}\right)+\ldots$ or $36 \times\left(8^{2 k+1}+6^{2 k-1}\right)+\ldots$ $=64 \times\left(8^{2 k+1}+6^{2 k-1}\right)-28 \times 6^{2 k-1}$ or $36 \times\left(8^{2 k+1}+6^{2 k-1}\right)+28 \times 8^{2 k+1}$
So if the result is true for n=k then it is true for n=k+1. As the result has
been shown to be true for n=1, then the result is true for all n.

A1cso

(5)

[Maximum number: 6]

Prove by induction that for $n \in \mathbb{Z}^{+}$

f(n)=7^{n-1}+8^{2 n+1}

is divisible by 57
(6)

For n=1, $f(1)=7^0+8^3=513=57\times9$ .
Assume $f(k)=7^{k-1}+8^{2k+1}$ is divisible by 57.
$f(k+1)-64f(k)=7^k+8^{2k+3}-64(7^{k-1}+8^{2k+1})$ $=7^{k-1}(7-64)=-57\cdot7^{k-1}$
Since 64f(k) and $57\cdot7^{k-1}$ are divisible by 57, f(k+1) is divisible by 57.
Therefore true for all positive integers n.

[Maximum number: 6]

Prove by induction that for all positive integers n

\sum_{r=1}^{n} \log (2 r-1)=\log \left(\frac{(2 n)!}{2^{n} n!}\right)

For $n=1, \sum_{r=1}^{1} \log (2 r-1)=\log (2-1)=\log 1$ and $\log \left(\frac{(2 \times 1)!}{2^{1}!!}\right)=\log 1$

So true for n=1
(Assume the result is true for n=k, so $\sum_{r=1}^{k} \log (2 r-1)=\log \left(\frac{(2 k)!}{2^{k} k!}\right)$ Then)
$\sum_{r=1}^{k+1} \log (2 r-1)=\log \left(\frac{(2 k)!}{2^{k} k!}\right)+\log (2(k+1)-1)$ $=\log \left(\frac{(2 k)!}{2^{k} k!} \times(2 k+1)\right)$ $=\log \left(\frac{(2 k+1)!}{2^{k} k!} \times \frac{2 k+2}{2 k+2}\right)=\log \left(\frac{(2 k+2)!}{2^{k} \times 2(k+1)!}\right)$ $=\log \left(\frac{(2 k+2)!}{2^{k+1}(k+1)!}\right)$
Hence result is true for n=k+1. As true for n=1 and have shown if true for
n=k then it is true for n=k+1, so it is true for all $n \in \mathbb{N}$ by induction.
(6)

(6 marks)

All question bank results loaded

Covered syllabus points

Question 1

Question (a)

Question (b)

Question 2

Question 3