4.01a Mathematical induction: construct proofs

Given that \(\mathbf{M} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}\), prove that \(\mathbf{M}^n = \begin{bmatrix} 3^{n-1} & 3^{n-1} & 3^{n-1} \\ 3^{n-1} & 3^{n-1} & 3^{n-1} \\ 3^{n-1} & 3^{n-1} & 3^{n-1} \end{bmatrix}\) for all \(n \in \mathbb{N}\) [5 marks]

Prove by induction that \(f(n) = n^3 + 3n^2 + 8n\) is divisible by 6 for all integers \(n \geq 1\) [7 marks]

The sequence \(u_1, u_2, u_3, \ldots\) is defined by $$u_1 = 0 \quad u_{n+1} = \frac{5}{6 - u_n}$$ Prove by induction that, for all integers \(n \geq 1\), $$u_n = \frac{5^n - 5}{5^n - 1}$$ [6 marks]

The function \(f\) is defined by $$f(n) = 3^{3n+1} + 2^{3n+4} \quad (n \in \mathbb{Z}^+)$$ Prove by induction that \(f(n)\) is divisible by 19 for \(n \geq 1\) [6 marks]

Prove that \(8^n - 7n + 6\) is divisible by 7 for all integers \(n \geq 0\) [5 marks]

Prove that \(n! > 2^{2n}\) for all integers \(n \geq 9\). [5]

Prove by induction that \(\begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix}^n = \begin{pmatrix} 1 & 2^n - 1 \\ 0 & 2^n \end{pmatrix}\) for all positive integers \(n\). [6]

You are given that matrix \(\mathbf{M} = \begin{pmatrix} -3 & 8 \\ -2 & 5 \end{pmatrix}\).

1. Prove that, for all positive integers \(n\), \(\mathbf{M}^n = \begin{pmatrix} 1-4n & 8n \\ -2n & 1+4n \end{pmatrix}\). [6]
2. Determine the equation of the line of invariant points of the transformation represented by the matrix \(\mathbf{M}\). [3]

It is claimed that the answer to part (ii) is also a line of invariant points of the transformation represented by the matrix \(\mathbf{M}^n\), for any positive integer \(n\).

1. Explain geometrically why this claim is true. [2]
2. Verify algebraically that this claim is true. [3]

Prove, by mathematical induction, that \(\sum_{r=1}^{n} r(r+3) = \frac{1}{3}n(n+1)(n+5)\) for all positive integers \(n\). [6]

Use mathematical induction to prove that \(4^n + 2\) is divisible by 6 for all positive integers \(n\). [7]

In this question you must show detailed reasoning. M is the matrix \(\begin{pmatrix} 1 & 6 \\ 0 & 2 \end{pmatrix}\). Prove that \(\mathbf{M}^n = \begin{pmatrix} 1 & 3(2^{n+1} - 2) \\ 0 & 2^n \end{pmatrix}\), for any positive integer \(n\). [6]

A series is given by $$\sum_{r=1}^k 9^{r-1}$$

1. Write down a formula for the sum of this series. [1]
2. Prove by induction that \(P(n) = 9^n - 8n - 1\) is divisible by 64 if \(n\) is a positive integer greater than 1. [4]

Prove by induction that, for \(n \geq 1\), \(\sum_{r=1}^n r(3r + 1) = n(n + 1)^2\). [5]

$$\text{M} = \begin{pmatrix} 2 & 3 \\ 0 & 1 \end{pmatrix}$$ [2] Prove by induction that \(\text{M}^n = \begin{pmatrix} 2^n & 3(2^n - 1) \\ 0 & 1 \end{pmatrix}\), for all positive integers \(n\). [6]

$$\mathbf{M} = \begin{pmatrix} 2 & 3 \\ 0 & 1 \end{pmatrix}.$$ Prove by induction that \(\mathbf{M}^n = \begin{pmatrix} 2^n & 3(2^n - 1) \\ 0 & 1 \end{pmatrix}\), for all positive integers \(n\). [6]

Prove by induction that, for \(n \in \mathbb{Z}^+\) $$f(n) = 2^{n+2} + 3^{2n+1}$$ is divisible by 7 [6]

A sequence is defined by \(U_n = 2^{n+1} + 9 \times 13^n\) for positive integer values of \(n\). Prove by induction that \(U_n\) is divisible by 11. [5]

Prove by induction that, for \(n \in \mathbb{Z}^+\), $$f(n) = 2^{2n-1} + 3^{2n-1} \text{ is divisible by 5}.$$ [6]

Prove by induction that, for all positive integers \(n\), \(7^n + 3^{n-1}\) is a multiple of \(4\). [5]

The matrix \(\mathbf{A}\) is given by \(\mathbf{A} = \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix}\).

1. Find \(\mathbf{A}^2\) and \(\mathbf{A}^3\). [3]
2. Hence suggest a suitable form for the matrix \(\mathbf{A}^n\). [1]
3. Use induction to prove that your answer to part (ii) is correct. [4]

Prove by induction that for \(n \in \mathbb{Z}^+\) $$f(n) = 4^{n+1} + 5^{2n-1}$$ is divisible by 21 [6]