4.01a Mathematical induction: construct proofs

1. Express \(\frac{6x + 10}{x + 3}\) in the form \(p + \frac{q}{x + 3}\), where \(p\) and \(q\) are integers to be found. [1]

The sequence of real numbers \(u_1, u_2, u_3, ...\) is such that \(u_1 = 5.2\) and \(u_{n+1} = \frac{6u_n + 10}{u_n + 3}\).

1. Prove by induction that \(u_n > 5\), for \(n \in \mathbb{Z}^+\). [4]

Prove that \(\sum_{r=1}^{n} (r - 1)(r + 2) = \frac{1}{3} (n - 1)n(n + 4)\). [6]

Prove by induction that, for \(n \in \mathbb{Z}^+\), \(\sum_{r=1}^{n} r 2^r = 2\{1 + (n - 1)2^n\}\). [5]

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

Given that \(f(n) = 3^{4n} + 2^{4n + 2}\),

1. show that, for \(k \in \mathbb{Z}^+\), \(f(k + 1) - f(k)\) is divisible by 15, [4]
2. prove that, for \(n \in \mathbb{Z}^+\), \(f (n)\) is divisible by 5. [3]

De Moivre's theorem states that \((\cos\theta + i\sin\theta)^n = \cos n\theta + i\sin n\theta\) for \(n \in \mathbb{R}\)

1. Use induction to prove de Moivre's theorem for \(n \in \mathbb{Z}^+\). (5)
2. Show that \(\cos 5\theta = 16\cos^5\theta - 20\cos^3\theta + 5\cos\theta\) (5)
3. Hence show that \(2\cos\frac{\pi}{10}\) is a root of the equation $$x^4 - 5x^2 + 5 = 0$$ (3)

The sequence \(u_1, u_2, u_3, \ldots\) is defined by \(u_1 = 2\) and \(u_{n+1} = \frac{u_n}{1 + u_n}\) for \(n \geq 1\).

1. Find \(u_2\) and \(u_3\), and show that \(u_4 = \frac{2}{7}\). [3]
2. Hence suggest an expression for \(u_n\). [2]
3. Use induction to prove that your answer to part (ii) is correct. [5]

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

Prove by induction that \(3 + 6 + 12 + \ldots + 3 \times 2^{n-1} = 3(2^n - 1)\) for all positive integers \(n\). [7]

Prove by induction that \(\sum_{r=1}^{n} 3^{r-1} = \frac{3^n - 1}{2}\). [6]

The polynomial \(\text{p}(n)\) is given by \(\text{p}(n) = (n-1)^3 + n^3 + (n+1)^3\).

1. 1. Show that \(\text{p}(k+1) - \text{p}(k)\), where \(k\) is a positive integer, is a multiple of 9. [3 marks]
   2. Prove by induction that \(\text{p}(n)\) is a multiple of 9 for all integers \(n \geqslant 1\). [4 marks]
2. Using the result from part (a)(ii), show that \(n(n^2 + 2)\) is a multiple of 3 for any positive integer \(n\). [2 marks]

Given that \(p \geq -1\), prove by induction that, for all integers \(n \geq 1\), $$(1 + p)^n \geq 1 + np$$ [6 marks]

A multiplicative group with identity \(e\) contains distinct elements \(a\) and \(r\), with the properties \(r^6 = e\) and \(ar = r^2a\).

1. Prove that \(rar = a\). [2]
2. Prove, by induction or otherwise, that \(r^n ar^n = a\) for all positive integers \(n\). [4]

\(\alpha\), \(\beta\) and \(\gamma\) are the real roots of the cubic equation $$x^3 + mx^2 + nx + 2 = 0$$ By considering \((\alpha - \beta)^2 + (\gamma - \alpha)^2 + (\beta - \gamma)^2\), prove that $$m^2 \geq 3n$$ [4 marks]

The matrix \(\mathbf{A}\) is given by $$\mathbf{A} = \begin{bmatrix} 1 & 2 \\ 0 & 3 \end{bmatrix}$$

1. Prove by induction that, for all integers \(n \geq 1\), $$\mathbf{A}^n = \begin{bmatrix} 1 & 3^n - 1 \\ 0 & 3^n \end{bmatrix}$$ [4 marks]
2. Find all invariant lines under the transformation matrix \(\mathbf{A}\). Fully justify your answer. [6 marks]
3. Find a line of invariant points under the transformation matrix \(\mathbf{A}\). [2 marks]

Prove by induction that, for all integers \(n \geq 1\), the expression \(7^n - 3^n\) is divisible by 4 [4 marks]

The matrix M is defined by \(\mathbf{M} = \begin{pmatrix} 3 & 2 & -2 \\ 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]

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