4.01a Mathematical induction: construct proofs

10. (i) A sequence of numbers \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\), is defined by $$u _ { n + 1 } = 5 u _ { n } + 3 , \quad u _ { 1 } = 3$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$u _ { n } = \frac { 3 } { 4 } \left( 5 ^ { n } - 1 \right)$$ (ii) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$f ( n ) = 5 \left( 5 ^ { n } \right) - 4 n - 5 \text { is divisible by } 16 .$$ \includegraphics[max width=\textwidth, alt={}, center]{9093bb1d-4f32-44e7-b0e7-b8c4f8a844e1-32_109_127_2473_1818} \includegraphics[max width=\textwidth, alt={}, center]{9093bb1d-4f32-44e7-b0e7-b8c4f8a844e1-32_205_1828_2553_122}

8. Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\),

1. \(\mathrm { f } ( n ) = 5 ^ { n } + 8 n + 3\) is divisible by 4 ,
2. \(\left( \begin{array} { l l } 3 & - 2 \\ 2 & - 1 \end{array} \right) ^ { n } = \left( \begin{array} { l r } 2 n + 1 & - 2 n \\ 2 n & 1 - 2 n \end{array} \right)\)

7. $$f ( n ) = 2 ^ { n } + 6 ^ { n }$$

1. Show that \(\mathrm { f } ( k + 1 ) = 6 \mathrm { f } ( k ) - 4 \left( 2 ^ { k } \right)\).
2. Hence, or otherwise, prove by induction that, for \(n \in \mathbb { Z } ^ { + } , \mathrm { f } ( n )\) is divisible by 8 .

9. (a) Prove by induction that $$\sum _ { r = 1 } ^ { n } r ^ { 2 } = \frac { 1 } { 6 } n ( n + 1 ) ( 2 n + 1 )$$ Using the standard results for \(\sum _ { r = 1 } ^ { n } r\) and \(\sum _ { r = 1 } ^ { n } r ^ { 2 }\),
(b) show that $$\sum _ { r = 1 } ^ { n } ( r + 2 ) ( r + 3 ) = \frac { 1 } { 3 } n \left( n ^ { 2 } + a n + b \right) ,$$ where \(a\) and \(b\) are integers to be found.
(c) Hence show that $$\sum _ { r = n + 1 } ^ { 2 n } ( r + 2 ) ( r + 3 ) = \frac { 1 } { 3 } n \left( 7 n ^ { 2 } + 27 n + 26 \right)$$

9. Prove by induction, that for \(n \in \mathbb { Z } ^ { + }\),

1. \(\left( \begin{array} { l l } 3 & 0 \\ 6 & 1 \end{array} \right) ^ { n } = \left( \begin{array} { c c } 3 ^ { n } & 0 \\ 3 \left( 3 ^ { n } - 1 \right) & 1 \end{array} \right)\),
2. \(\mathrm { f } ( n ) = 7 ^ { 2 n - 1 } + 5\) is divisible by 12 .

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

5. Prove, by induction, that \(3 ^ { 2 n } + 7\) is divisible by 8 for all positive integers \(n\).

9. (a) A sequence of numbers is defined by $$\begin{aligned} & u _ { 1 } = 8 \\ & u _ { n + 1 } = 4 u _ { n } - 9 n , \quad n \geqslant 1 \end{aligned}$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$u _ { n } = 4 ^ { n } + 3 n + 1$$ (b) Prove by induction that, for \(m \in \mathbb { Z } ^ { + }\), $$\left( \begin{array} { l l } 3 & - 4 \\ 1 & - 1 \end{array} \right) ^ { m } = \left( \begin{array} { c c } 2 m + 1 & - 4 m \\ m & 1 - 2 m \end{array} \right)$$

9. (a) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$\sum _ { r = 1 } ^ { n } ( r + 1 ) 2 ^ { r - 1 } = n 2 ^ { n }$$ (b) A sequence of numbers is defined by $$\begin{gathered} u _ { 1 } = 0 , \quad u _ { 2 } = 32 , \\ u _ { n + 2 } = 6 u _ { n + 1 } - 8 u _ { n } \quad n \geqslant 1 \end{gathered}$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$u _ { n } = 4 ^ { n + 1 } - 2 ^ { n + 3 }$$

9. Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$f ( n ) = 8 ^ { n } - 2 ^ { n }$$ is divisible by 6

1. (i) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\),

$$\left( \begin{array} { r r } 1 & 0 \\ - 1 & 5 \end{array} \right) ^ { n } = \left( \begin{array} { c c } 1 & 0 \\ - \frac { 1 } { 4 } \left( 5 ^ { n } - 1 \right) & 5 ^ { n } \end{array} \right)$$ (ii) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$\sum _ { r = 1 } ^ { n } ( 2 r - 1 ) ^ { 2 } = \frac { 1 } { 3 } n \left( 4 n ^ { 2 } - 1 \right)$$

8. (i) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$\sum _ { r = 1 } ^ { n } \frac { 2 r + 1 } { r ^ { 2 } ( r + 1 ) ^ { 2 } } = 1 - \frac { 1 } { ( n + 1 ) ^ { 2 } }$$ (ii) A sequence of positive rational numbers is defined by $$\begin{aligned} u _ { 1 } & = 3 \\ u _ { n + 1 } & = \frac { 1 } { 3 } u _ { n } + \frac { 8 } { 9 } , \quad n \in \mathbb { Z } ^ { + } \end{aligned}$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$u _ { n } = 5 \times \left( \frac { 1 } { 3 } \right) ^ { n } + \frac { 4 } { 3 }$$

9. (i) A sequence of numbers is defined by $$\begin{gathered} u _ { 1 } = 6 , \quad u _ { 2 } = 27 \\ u _ { n + 2 } = 6 u _ { n + 1 } - 9 u _ { n } \quad n \geqslant 1 \end{gathered}$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$u _ { n } = 3 ^ { n } ( n + 1 )$$ (ii) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$f ( n ) = 3 ^ { 3 n - 2 } + 2 ^ { 3 n + 1 } \text { is divisible by } 19$$ \includegraphics[max width=\textwidth, alt={}, center]{536d7ec7-91b0-4fda-a485-2ac4a72c7d59-29_56_20_109_1950}

1. Prove by induction that

$$f ( n ) = 2 ^ { n + 2 } + 3 ^ { 2 n + 1 }$$ is divisible by 7 for all positive integers \(n\).

9. (a) A sequence of numbers is defined by $$u _ { 1 } = 3 \text { and } u _ { n + 1 } = 3 u _ { n } + 4 \text { for } n \geqslant 1 .$$ Prove by induction that $$u _ { n } = 3 ^ { n } + 2 \left( 3 ^ { n - 1 } - 1 \right) \text { for } n \in \mathbb { Z } ^ { + } \text {. }$$ (b) $$\mathbf { A } = \left( \begin{array} { l l } 4 & 0 \\ 9 & 1 \end{array} \right)$$

1. Prove by induction that $$\mathbf { A } ^ { n } = \left( \begin{array} { c c } 4 ^ { n } & 0 \\ 3 \left( 4 ^ { n } - 1 \right) & 1 \end{array} \right) \text { for } n \in \mathbb { Z } ^ { + } .$$
2. Determine whether the result \(\mathbf { A } ^ { n } = \left( \begin{array} { c c } 4 ^ { n } & 0 \\ 3 \left( 4 ^ { n } - 1 \right) & 1 \end{array} \right)\) is also valid for \(n = - 1\).

9. Use the method of mathematical induction to prove that, for \(n \in \mathbb { Z } ^ { + }\),

1. \(\left( \begin{array} { c c } 2 & 1 \\ - 1 & 0 \end{array} \right) ^ { n } = \left( \begin{array} { c c } n + 1 & n \\ - n & 1 - n \end{array} \right)\)
2. \(\mathrm { f } ( n ) = 4 ^ { n } + 6 n - 1\) is divisible by 3 .

4. (a) Given that $$z = r ( \cos \theta + \mathrm { i } \sin \theta ) , \quad r \in \mathbb { R }$$ prove, by induction, that \(z ^ { n } = r ^ { n } ( \cos n \theta + \mathrm { i } \sin n \theta ) , \quad n \in \mathbb { Z } ^ { + }\) $$w = 3 \left( \cos \frac { 3 \pi } { 4 } + i \sin \frac { 3 \pi } { 4 } \right)$$ (b) Find the exact value of \(w ^ { 5 }\), giving your answer in the form \(a + \mathrm { i } b\), where \(a , b \in \mathbb { R }\).

2 Prove by induction that, for \(n \geqslant 1 , \sum _ { r = 1 } ^ { n } r ^ { 2 } = \frac { 1 } { 6 } n ( n + 1 ) ( 2 n + 1 )\).

6 The sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by \(u _ { n } = n ^ { 2 } + 3 n\), for all positive integers \(n\).

1. Show that \(u _ { n + 1 } - u _ { n } = 2 n + 4\).
2. Hence prove by induction that each term of the sequence is divisible by 2 .

8 The sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by \(u _ { 1 } = 1\) and \(u _ { n + 1 } = u _ { n } + 2 n + 1\).

1. Show that \(u _ { 4 } = 16\).
2. Hence suggest an expression for \(u _ { n }\).
3. Use induction to prove that your answer to part (ii) is correct.

7 The matrix \(\mathbf { A }\) is given by \(\mathbf { A } = \left( \begin{array} { l l } 2 & 0 \\ 0 & 1 \end{array} \right)\).

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

2 Prove by induction that, for \(n \geqslant 1 , \sum _ { r = 1 } ^ { n } r ^ { 3 } = \frac { 1 } { 4 } n ^ { 2 } ( n + 1 ) ^ { 2 }\).

3

1. Show that \(\frac { 1 } { r ! } - \frac { 1 } { ( r + 1 ) ! } = \frac { r } { ( r + 1 ) ! }\).
2. Hence find an expression, in terms of \(n\), for $$\frac { 1 } { 2 ! } + \frac { 2 } { 3 ! } + \frac { 3 } { 4 ! } + \ldots + \frac { n } { ( n + 1 ) ! }$$

4 The matrix \(\mathbf { A }\) is given by \(\mathbf { A } = \left( \begin{array} { l l } 3 & 1 \\ 0 & 1 \end{array} \right)\). Prove by induction that, for \(n \geqslant 1\), $$\mathbf { A } ^ { n } = \left( \begin{array} { c c } 3 ^ { n } & \frac { 1 } { 2 } \left( 3 ^ { n } - 1 \right) \\ 0 & 1 \end{array} \right)$$

4 The matrix \(\mathbf { M }\) is given by \(\mathbf { M } = \left( \begin{array} { l l } 2 & 2 \\ 0 & 1 \end{array} \right)\). Prove by induction that, for \(n \geqslant 1\), $$\mathbf { M } ^ { n } = \left( \begin{array} { c c } 2 ^ { n } & 2 ^ { n + 1 } - 2 \\ 0 & 1 \end{array} \right) .$$