4.01a Mathematical induction: construct proofs

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

1. Prove by induction that for all positive integers \(n\)

$$\sum _ { r = 1 } ^ { n } \log ( 2 r - 1 ) = \log \left( \frac { ( 2 n ) ! } { 2 ^ { n } n ! } \right)$$

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

$$\left( \begin{array} { r r } 5 & - 1 \\ 4 & 1 \end{array} \right) ^ { n } = 3 ^ { n - 1 } \left( \begin{array} { c c } 2 n + 3 & - n \\ 4 n & 3 - 2 n \end{array} \right)$$ (ii) Prove by induction that for \(n \in \mathbb { Z } ^ { + }\) $$f ( n ) = 8 ^ { 2 n + 1 } + 6 ^ { 2 n - 1 }$$ is divisible by 7

9. (i) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$\sum _ { r = 1 } ^ { n } r ( r + 1 ) ( r + 2 ) = \frac { n ( n + 1 ) ( n + 2 ) ( n + 3 ) } { 4 }$$ (ii) Prove by induction that, $$4 ^ { n } + 6 n + 8 \text { is divisible by } 18$$ for all positive integers \(n\). \includegraphics[max width=\textwidth, alt={}, center]{df5ab400-5cb1-4b51-8b0a-52dc3587f81a-16_62_44_2476_1889}

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

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

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 } }$$

3. Prove by induction that for \(n \in \mathbb { Z } ^ { + }\) $$\sum _ { r = 1 } ^ { n } \frac { 2 } { r ( r + 1 ) ( r + 2 ) } = \frac { 1 } { 2 } - \frac { 1 } { ( n + 1 ) ( n + 2 ) }$$

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

$$\left( \begin{array} { l l } a & 0 \\ 1 & b \end{array} \right) ^ { n } = \left( \begin{array} { c c } a ^ { n } & 0 \\ \frac { a ^ { n } - b ^ { n } } { a - b } & b ^ { n } \end{array} \right)$$ where \(a\) and \(b\) are constants and \(a \neq b\).

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

$$\sum _ { r = 1 } ^ { n } \frac { 2 r ^ { 2 } - 1 } { r ^ { 2 } ( r + 1 ) ^ { 2 } } = \frac { n ^ { 2 } } { ( n + 1 ) ^ { 2 } }$$ (ii) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$f ( n ) = 12 ^ { n } + 2 \times 5 ^ { n - 1 }$$ is divisible by 7 \includegraphics[max width=\textwidth, alt={}, center]{a3457c24-fbda-413d-b3b2-6be375307318-29_2255_50_314_34}
\includegraphics[max width=\textwidth, alt={}, center]{a3457c24-fbda-413d-b3b2-6be375307318-31_2255_50_314_34}

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

1. Prove, by induction, that for \(n \in \mathbb { Z } , n \geqslant 2\)

$$4 ^ { n } + 6 n - 10$$ is divisible by 18

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

$$\left( \begin{array} { l l } 1 & r \\ 0 & 2 \end{array} \right) ^ { n } = \left( \begin{array} { c c } 1 & \left( 2 ^ { n } - 1 \right) r \\ 0 & 2 ^ { n } \end{array} \right)$$ where \(r\) is a constant. $$\mathbf { M } = \left( \begin{array} { l l } 4 & 0 \\ 0 & 5 \end{array} \right) \quad \mathbf { N } = \left( \begin{array} { r r } 1 & - 2 \\ 0 & 2 \end{array} \right) ^ { 4 }$$ The transformation represented by matrix \(\mathbf { M }\) followed by the transformation represented by matrix \(\mathbf { N }\) is represented by the matrix \(\mathbf { B }\) (b) (i) Determine \(\mathbf { N }\) in the form \(\left( \begin{array} { l l } a & b \\ c & d \end{array} \right)\) where \(a , b , c\) and \(d\) are integers.
(ii) Determine B Hexagon \(S\) is transformed onto hexagon \(S ^ { \prime }\) by matrix \(\mathbf { B }\) (c) Given that the area of \(S ^ { \prime }\) is 720 square units, determine the area of \(S\)

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

$$f ( n ) = 7 ^ { n - 1 } + 8 ^ { 2 n + 1 }$$ is divisible by 57
(6)

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

1. (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. Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\),

$$\mathrm { f } ( n ) = 5 ^ { n } + 8 n + 3 \text { is divisible by } 4$$

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

4. Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\), $$\sum _ { r = 1 } ^ { n } \frac { 1 } { r ( r + 1 ) } = \frac { n } { n + 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\).

8. (a) Prove by induction that, for any positive integer \(n\), $$\sum _ { r = 1 } ^ { n } r ^ { 3 } = \frac { 1 } { 4 } n ^ { 2 } ( n + 1 ) ^ { 2 }$$ (b) Using the formulae for \(\sum _ { r = 1 } ^ { n } r\) and \(\sum _ { r = 1 } ^ { n } r ^ { 3 }\), show that $$\sum _ { r = 1 } ^ { n } \left( r ^ { 3 } + 3 r + 2 \right) = \frac { 1 } { 4 } n ( n + 2 ) \left( n ^ { 2 } + 7 \right)$$ (c) Hence evaluate \(\sum _ { r = 15 } ^ { 25 } \left( r ^ { 3 } + 3 r + 2 \right)\)

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)$$

6. (a) Prove by induction $$\sum _ { r = 1 } ^ { n } r ^ { 3 } = \frac { 1 } { 4 } n ^ { 2 } ( n + 1 ) ^ { 2 }$$ (b) Using the result in part (a), show that $$\sum _ { r = 1 } ^ { n } \left( r ^ { 3 } - 2 \right) = \frac { 1 } { 4 } n \left( n ^ { 3 } + 2 n ^ { 2 } + n - 8 \right)$$ (c) Calculate the exact value of \(\sum _ { r = 20 } ^ { 50 } \left( r ^ { 3 } - 2 \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 } ^ { + }$$