Prove recurrence relation formula

2 The sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is such that \(u _ { 1 } = 1\) and \(\mathrm { u } _ { \mathrm { n } + 1 } = 2 \mathrm { u } _ { \mathrm { n } } + 1\) for \(n \geqslant 1\).

1. Prove by induction that \(u _ { n } = 2 ^ { n } - 1\) for all positive integers \(n\).
2. Deduce that \(\mathrm { u } _ { 2 \mathrm { n } }\) is divisible by \(\mathrm { u } _ { \mathrm { n } }\) for \(n \geqslant 1\).

1 The sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is such that \(u _ { 1 } = 4\) and \(u _ { n + 1 } = 3 u _ { n } - 2\) for \(n \geqslant 1\).
Prove by induction that \(u _ { n } = 3 ^ { n } + 1\) for all positive integers \(n\).

1. (i) A sequence of numbers is defined by

$$\begin{gathered} u _ { 1 } = 5 \quad u _ { 2 } = 13 \\ u _ { n + 2 } = 5 u _ { n + 1 } - 6 u _ { n } \quad n \geqslant 1 \end{gathered}$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$u _ { n } = 2 ^ { n } + 3 ^ { n }$$ (ii) Prove by induction that for \(n \geqslant 2\), where \(n \in \mathbb { Z }\), $$f ( n ) = 7 ^ { 2 n } - 48 n - 1$$ is divisible by 2304 \includegraphics[max width=\textwidth, alt={}, center]{864a8956-ead0-4abd-91f4-1caa6d17f5e8-14_106_58_2403_1884}

8. (i) A sequence of numbers is defined by $$\begin{aligned} u _ { 1 } & = 3 \\ u _ { n + 1 } & = u _ { n } + 3 n - 2 \quad n \geqslant 1 \end{aligned}$$ Prove by induction that, for all positive integers \(n\), $$u _ { n } = \frac { 3 } { 2 } n ^ { 2 } - \frac { 7 } { 2 } n + 5$$ (ii) Prove by induction that, for all positive integers \(n\), $$f ( n ) = 3 ^ { 2 n + 3 } + 40 n - 27 \text { is divisible by } 64$$

9. (i) A sequence of numbers \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by $$u _ { n + 1 } = \frac { 1 } { 3 } \left( 2 u _ { n } - 1 \right) \quad u _ { 1 } = 1$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$u _ { n } = 3 \left( \frac { 2 } { 3 } \right) ^ { n } - 1$$ (ii) \(\mathrm { f } ( n ) = 2 ^ { n + 2 } + 3 ^ { 2 n + 1 }\) Prove by induction that, for \(n \in \mathbb { Z } ^ { + } , \mathrm { f } ( n )\) is a multiple of 7

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

1. (i) A sequence of numbers is defined by

$$\begin{gathered} u _ { 1 } = 3 \\ u _ { n + 1 } = 2 u _ { n } - 2 ^ { n + 1 } \quad n \geqslant 1 \end{gathered}$$ Prove by induction that, for \(n \in \mathbb { N }\) $$u _ { n } = 5 \times 2 ^ { n - 1 } - n \times 2 ^ { n }$$ (ii) Prove by induction that, for \(n \in \mathbb { N }\) $$f ( n ) = 5 ^ { n + 2 } - 4 n - 9$$ is divisible by 16

9. (i) A sequence of numbers is defined by $$\begin{gathered} u _ { 1 } = 0 \quad u _ { 2 } = - 6 \\ u _ { n + 2 } = 5 u _ { n + 1 } - 6 u _ { n } \quad n \geqslant 1 \end{gathered}$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$u _ { n } = 3 \times 2 ^ { n } - 2 \times 3 ^ { n }$$ (ii) Prove by induction that, for all positive integers \(n\), $$f ( n ) = 3 ^ { 3 n - 2 } + 2 ^ { 4 n - 1 }$$ is divisible by 11

6. A series of positive integers \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by $$u _ { 1 } = 6 \text { and } u _ { n + 1 } = 6 u _ { n } - 5 , \text { for } n \geq 1 .$$ Prove by induction that \(u _ { n } = 5 \times 6 ^ { n - 1 } + 1\), for \(n \geq 1\).

6. A series of positive integers \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by $$u _ { 1 } = 6 \text { and } u _ { n + 1 } = 6 u _ { n } - 5 , \text { for } n \geqslant 1 .$$ Prove by induction that \(u _ { n } = 5 \times 6 ^ { n - 1 } + 1\), for \(n \geqslant 1\).

6. A series of positive integers \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by $$u _ { 1 } = 6 \text { and } u _ { n + 1 } = 6 u _ { n } - 5 \text {, for } n \geqslant 1 \text {. }$$ Prove by induction that \(u _ { n } = 5 \times 6 ^ { n - 1 } + 1\), for \(n \geqslant 1\).

3. A sequence of numbers is defined by $$\begin{aligned} u _ { 1 } & = 2 \\ u _ { n + 1 } & = 5 u _ { n } - 4 , \quad n \geqslant 1 . \end{aligned}$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + } , u _ { n } = 5 ^ { n - 1 } + 1\).

9. A sequence of numbers \(u _ { 1 } , u _ { 2 } , u _ { 3 } , u _ { 4 } , \ldots\) is defined by $$u _ { n + 1 } = 4 u _ { n } + 2 , \quad u _ { 1 } = 2$$ Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$u _ { n } = \frac { 2 } { 3 } \left( 4 ^ { n } - 1 \right)$$

7. A sequence can be described by the recurrence formula $$u _ { n + 1 } = 2 u _ { n } + 1 , \quad n \geqslant 1 , \quad u _ { 1 } = 1$$

1. Find \(u _ { 2 }\) and \(u _ { 3 }\).
2. Prove by induction that \(u _ { n } = 2 ^ { n } - 1\)

8. (a) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$\sum _ { r = 1 } ^ { n } r ( r + 3 ) = \frac { 1 } { 3 } n ( n + 1 ) ( n + 5 )$$ (b) A sequence of positive integers is defined by $$\begin{aligned} u _ { 1 } & = 1 \\ u _ { n + 1 } & = u _ { n } + n ( 3 n + 1 ) , \quad n \in \mathbb { Z } ^ { + } \end{aligned}$$ Prove by induction that $$u _ { n } = n ^ { 2 } ( n - 1 ) + 1 , \quad n \in \mathbb { Z } ^ { + }$$

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}

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. (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}

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\).

6 A sequence is defined by \(a _ { 1 } = 7\) and \(a _ { k + 1 } = 7 a _ { k } - 3\).

1. Calculate the value of the third term, \(a _ { 3 }\).
2. Prove by induction that \(a _ { n } = \frac { \left( 13 \times 7 ^ { n - 1 } \right) + 1 } { 2 }\).

3 The sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by \(u _ { 1 } = 2\), and \(u _ { n + 1 } = 2 u _ { n } - 1\) for \(n \geqslant 1\). Prove by induction that \(u _ { n } = 2 ^ { n - 1 } + 1\).

5 The sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by $$u _ { 1 } = 5 \text { and } u _ { n + 1 } = 3 u _ { n } + 2 \text { for } n \geqslant 1 \text {. }$$ Prove by induction that \(u _ { n } = 2 \times 3 ^ { n } - 1\).

6 A sequence is defined by \(u _ { 1 } = 5\) and \(u _ { n + 1 } = u _ { n } + 2 ^ { n + 1 }\). Prove by induction that \(u _ { n } = 2 ^ { n + 1 } + 1\).

6 A sequence is defined by \(u _ { 1 } = 2\) and \(u _ { n + 1 } = \frac { u _ { n } } { 1 + u _ { n } }\).

1. Calculate \(u _ { 3 }\).
2. Prove by induction that \(u _ { n } = \frac { 2 } { 2 n - 1 }\). Section B (36 marks)

6 A sequence is defined by \(a _ { 1 } = 1\) and \(a _ { k + 1 } = 3 \left( a _ { k } + 1 \right)\).

1. Calculate the value of the third term, \(a _ { 3 }\).
2. Prove by induction that \(a _ { n } = \frac { 5 \times 3 ^ { n - 1 } - 3 } { 2 }\).