4.01a Mathematical induction: construct proofs

The matrix \(\mathbf{M}\) is defined by \(\mathbf{M} = \begin{pmatrix} 3 & 2 & -2 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\) $$\mathbf{M}^n = \begin{pmatrix} 3^n & 3^n - 1 & -3^n + 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$ Prove by induction that \(\mathbf{M}^n = \begin{pmatrix} 3^n & 3^n - 1 & -3^n + 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\) for all integers \(n \geq 1\) [5 marks]

Prove that $$\sum_{r=1}^{n} 18(r^2 - 4) = n(6n^2 + 9n - 69).$$ [4 marks]

Prove that for all \(n \in \mathbb{N}\) $$\begin{pmatrix} 3 & 4i \\ i & -1 \end{pmatrix}^n = \begin{pmatrix} 2n+1 & 4ni \\ ni & 1-2n \end{pmatrix}$$ [6]

Prove by induction that for all positive integers \(n\) $$f(n) = 3^{2n+4} - 2^{2n}$$ is divisible by 5 [6]

Prove by induction that \(2^{n+1} + 5 \times 9^n\) is divisible by 7 for all integers \(n \geq 1\). [6]

Prove that \(2^{3n} - 3^n\) is divisible by 5 for all integers \(n \geq 1\). [5]

A sequence \(u_n\) is defined by \(u_{n+1} = 2u_n + 3\) and \(u_1 = 1\). Prove by induction that \(u_n = 4 \times 2^{n-1} - 3\) for all positive integers \(n\). [5]

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]

Prove by induction that \(11 \times 7^n - 13^n - 1\) is divisible by \(3\), for all integers \(n > 0\). [5]

Prove by induction that \(f(n) = 2^{4n} + 5^{2n} + 7^n\) is divisible by 3 for all positive integers \(n\). [5]

Prove by mathematical induction that \(\sum_{r=1}^{n} (r \times r!) = (n+1)! - 1\) for all positive integers \(n\). [6]

Prove by mathematical induction that \(\sum_{r=1}^{n}(r \times r!) = (n + 1)! - 1\) for all positive integers \(n\). [6]

Prove by induction that, for all positive integers \(n\), $$\sum_{r=1}^{n}(2r-1)^2 = \frac{1}{3}n(4n^2-1)$$ [6]

Prove by induction that \(7 \times 9^n - 15\) is divisible by \(4\), for all integers \(n \geq 0\). [5]

Prove by induction that \(11 \times 7^n - 13^n - 1\) is divisible by 3, for all integers \(n \geq 0\). [5]

Prove by induction that, for all positive integers \(n\), $$\sum_{r=1}^{n}(2r-1)^2 = \frac{1}{3}n(4n^2-1)$$ [6]

Prove by induction that \(2^{n+1} + 5 \times 9^n\) is divisible by 7 for all integers \(n \geq 1\). [6]

Prove by induction that \(n! \geq 6n\) for \(n \geq 4\). [5]

Prove that \(n! > 2^n\) for \(n \geq 4\). [5]

Let \(f(n) = 2(5^{n-1} + 1)\) for integers \(n = 1, 2, 3, \ldots\).

1. Prove that, if \(f(n)\) is divisible by 8, then \(f(n + 1)\) is also divisible by 8. [3]
2. Explain why this result does not imply that the statement '\(f(n)\) is divisible by 8 for all positive integers \(n\)' follows by mathematical induction. [1]

\(\mathbf{M}\) is the matrix \(\begin{pmatrix} 1 & -2 & 2 \\ 2 & -1 & 2 \\ 2 & -2 & 3 \end{pmatrix}\). Use induction to prove that, for all positive integers \(n\), $$\mathbf{M}^n \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 2n + 1 \\ 2n^2 + 2n \\ 2n^2 + 2n + 1 \end{pmatrix}.$$ [6]

It is given that $$\mathrm{f}(n) = 7^n (6n + 1) - 1.$$ By considering \(\mathrm{f}(n + 1) - \mathrm{f}(n)\), prove by induction that \(\mathrm{f}(n)\) is divisible by 12 for all positive integers \(n\). [6]