Proof by induction: Practice Questions

A sequence of matrices is defined by \(\mathbf{M}_n = \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}\) for \(n \ge 1\). To prove that \(\mathbf{M}_n \mathbf{M}_1 = \mathbf{M}_{n+1}\) using induction, what is the resulting product of \(\begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\)?

Use mathematical induction to prove that for all positive integers \(n\), the matrix \(\mathbf{M} = \begin{pmatrix} 3 & 1 \\ 0 & 2 \end{pmatrix}^n\) is given by:

A sequence of numbers \(u_n\) is defined by \(u_1 = 1\) and \(u_{n+1} = \frac{u_n}{1 + 3u_n}\) for \(n \ge 1\). It is conjectured that \(u_n = \frac{1}{3n - 2}\). To prove this by induction, if we assume the result for \(n = k\), which expression must be simplified to show the result for \(n = k+1\)?

Use mathematical induction to prove that \(n^3 + 2n\) is divisible by \(k\) for all positive integers \(n\). What is the largest integer value of \(k\)?

Prove by mathematical induction that for all positive integers \(n\), the matrix \(\mathbf{M}^n = \begin{pmatrix} 1 & 3 \\ 0 & 1 \end{pmatrix}^n\) is given by \(\begin{pmatrix} 1 & 3n \\ 0 & 1 \end{pmatrix}\).

Use mathematical induction to prove that \(\sum_{r=1}^n r \cdot r! = (n+1)! - 1\) for all positive integers \(n\).

Use mathematical induction to prove that \(5^{2n} - 1\) is divisible by \(24\) for all integers \(n \ge 1\).

A sequence of numbers \(u_1, u_2, u_3, \dots\) is defined by \(u_1 = 5\) and \(u_{n+1} = 2u_n - 3n + 1\) for \(n \ge 1\).

(a) Find expressions for \(u_2\) and \(u_3\).
(b) Use the method of mathematical induction to prove that \(u_n = 2^n + 3n\) for all positive integers \(n\).

Use the method of mathematical induction to prove that \(7^n + 3n - 1\) is divisible by \(9\) for all non-negative integers \(n\).