4.01a Mathematical induction: construct proofs

6 Let \(\mathbf { A } = \left( \begin{array} { l l } 2 & 0 \\ 1 & 1 \end{array} \right)\).

1. The transformation in the \(x - y\) plane represented by \(\mathbf { A } ^ { - 1 }\) transforms a triangle of area \(30 \mathrm {~cm} ^ { 2 }\) into a triangle of area \(d \mathrm {~cm} ^ { 2 }\). Find the value of \(d\).
2. Prove by mathematical induction that, for all positive integers \(n\), $$\mathbf { A } ^ { n } = \left( \begin{array} { c c } 2 ^ { n } & 0 \\ 2 ^ { n } - 1 & 1 \end{array} \right)$$
3. The line \(y = 2 x\) is invariant under the transformation in the \(x - y\) plane represented by \(\mathbf { A } ^ { n } \mathbf { B }\), where \(\mathbf { B } = \left( \begin{array} { r l } 1 & 0 \\ 33 & 0 \end{array} \right)\). Find the value of \(n\).

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 Prove by mathematical induction that \(2 ^ { 4 n } + 31 ^ { n } - 2\) is divisible by 15 for all positive integers \(n\).

3

1. Prove by mathematical induction that, for all positive integers \(n\), $$\sum _ { r = 1 } ^ { n } \left( 5 r ^ { 4 } + r ^ { 2 } \right) = \frac { 1 } { 2 } n ^ { 2 } ( n + 1 ) ^ { 2 } ( 2 n + 1 )$$
2. Use the result given in part (a) together with the List of formulae (MF19) to find \(\sum _ { \mathrm { r } = 1 } ^ { \mathrm { n } } \mathrm { r } ^ { 4 }\) in terms of \(n\), fully factorising your answer.

3 The sequence of positive numbers \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is such that \(u _ { 1 } > 4\) and, for \(n \geqslant 1\), $$u _ { n + 1 } = \frac { u _ { n } ^ { 2 } + u _ { n } + 12 } { 2 u _ { n } }$$

1. By considering \(\mathrm { u } _ { \mathrm { n } + 1 } - 4\), or otherwise, prove by mathematical induction that \(\mathrm { u } _ { \mathrm { n } } > 4\) for all positive integers \(n\).
2. Show that \(u _ { n + 1 } < u _ { n }\) for \(n \geqslant 1\).

5 Let \(\mathbf { A } = \left( \begin{array} { l l } 1 & a \\ 0 & 1 \end{array} \right)\), where \(a\) is a positive constant.

1. State the type of the geometrical transformation in the \(x - y\) plane represented by \(\mathbf { A }\).
2. Prove by mathematical induction that, for all positive integers \(n\), $$\mathbf { A } ^ { \mathrm { n } } = \left( \begin{array} { c c } 1 & \mathrm { na } \\ 0 & 1 \end{array} \right)$$ Let \(\mathbf { B } = \left( \begin{array} { c c } b & b \\ a ^ { - 1 } & a ^ { - 1 } \end{array} \right)\), where \(b\) is a positive constant.
3. Find the equations of the invariant lines, through the origin, of the transformation in the \(x - y\) plane represented by \(\mathbf { A } ^ { n } \mathbf { B }\).

1 Let \(\mathbf { A } = \left( \begin{array} { l l } 3 & 0 \\ 1 & 1 \end{array} \right)\).

1. Prove by mathematical induction that, for all positive integers \(n\), $$2 \mathbf { A } ^ { n } = \left( \begin{array} { l l } 2 \times 3 ^ { n } & 0 \\ 3 ^ { n } - 1 & 2 \end{array} \right)$$ \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\)
2. Find, in terms of \(n\), the inverse of \(\mathbf { A } ^ { n }\). \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\)

1 Prove by mathematical induction that, for all positive integers \(n , 5 ^ { 3 n } + 32 ^ { n } - 33\) is divisible by 31 .

2 Prove by mathematical induction that \(6 ^ { 4 n } + 38 ^ { n } - 2\) is divisible by 74 for all positive integers \(n\).

4

1. Prove by mathematical induction that, for all positive integers \(n\), $$\sum _ { r = 1 } ^ { n } r ^ { 2 } = \frac { 1 } { 6 } n ( n + 1 ) ( 2 n + 1 )$$ \includegraphics[max width=\textwidth, alt={}, center]{7eb2abb1-68f4-4cc8-8314-f436906d6c4e-08_2716_35_143_2012} The sum \(S _ { n }\) is defined by \(S _ { n } = \sum _ { r = 1 } ^ { n } r ^ { 4 }\).
2. Using the identity $$( 2 r + 1 ) ^ { 5 } - ( 2 r - 1 ) ^ { 5 } \equiv 160 r ^ { 4 } + 80 r ^ { 2 } + 2$$ show that \(S _ { n } = \frac { 1 } { 30 } n ( n + 1 ) ( 2 n + 1 ) \left( 3 n ^ { 2 } + 3 n - 1 \right)\).
3. Find the value of \(\lim _ { n \rightarrow \infty } \left( n ^ { - 5 } S _ { n } \right)\).

5 Prove by mathematical induction that, for every positive integer \(n\), $$\frac { d ^ { 2 n - 1 } } { d x ^ { 2 n - 1 } } ( x \sin x ) = ( - 1 ) ^ { n - 1 } ( x \cos x + ( 2 n - 1 ) \sin x )$$

2 Prove by mathematical induction that \(7 ^ { 2 n } - 1\) is divisible by 12 for every positive integer \(n\).

3 The sequence of real numbers \(a _ { 1 } , a _ { 2 } , a _ { 3 } , \ldots\) is such that \(a _ { 1 } = 1\) and $$a _ { n + 1 } = \left( a _ { n } + \frac { 1 } { a _ { n } } \right) ^ { 3 }$$

1. Prove by mathematical induction that \(\ln a _ { n } \geqslant 3 ^ { n - 1 } \ln 2\) for all integers \(n \geqslant 2\).
   [0pt] [You may use the fact that \(\ln \left( x + \frac { 1 } { x } \right) > \ln x\) for \(x > 0\).]
2. Show that \(\ln \mathrm { a } _ { \mathrm { n } + 1 } - \ln \mathrm { a } _ { \mathrm { n } } > 3 ^ { \mathrm { n } - 1 } \ln 4\) for \(n \geqslant 2\).

2 It is given that \(\mathrm { y } = \mathrm { xe } ^ { \mathrm { ax } }\), where \(a\) is a constant.
Prove by mathematical induction that, for all positive integers \(n\), $$\frac { d ^ { n } y } { d x ^ { n } } = \left( a ^ { n } x + n a ^ { n - 1 } \right) e ^ { a x }$$

2 Prove by mathematical induction that, for all positive integers \(n , 7 ^ { 2 n } + 97 ^ { n } - 50\) is divisible by 48. [6]

4 The function f is such that \(\mathrm { f } ^ { \prime \prime } ( x ) = \mathrm { f } ( x )\).
Prove by mathematical induction that, for every positive integer \(n\), $$\frac { d ^ { 2 n - 1 } } { d x ^ { 2 n - 1 } } ( x f ( x ) ) = x f ^ { \prime } ( x ) + ( 2 n - 1 ) f ( x )$$

2 Prove by mathematical induction that, for all positive integers \(n\), $$1 + 2 x + 3 x ^ { 2 } + \ldots + n x ^ { n - 1 } = \frac { 1 - ( n + 1 ) x ^ { n } + n x ^ { n + 1 } } { ( 1 - x ) ^ { 2 } }$$

2 Prove by mathematical induction that, for all positive integers \(n\), $$\frac { d ^ { n } } { d x ^ { n } } \left( x ^ { 2 } e ^ { x } \right) = \left( x ^ { 2 } + 2 n x + n ( n - 1 ) \right) e ^ { x }$$

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

2 It is given that \(\phi ( n ) = 5 ^ { n } ( 4 n + 1 ) - 1\), for \(n = 1,2,3 , \ldots\).
Prove, by mathematical induction, that \(\phi ( n )\) is divisible by 8 for every positive integer \(n\).

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

$$f ( n ) = 7 ^ { n } - 2 ^ { n } \text { is divisible by } 5$$

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}

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

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

$$\sum _ { r = 1 } ^ { n } \left( 4 r ^ { 3 } - 3 r ^ { 2 } + r \right) = n ^ { 3 } ( n + 1 )$$ (ii) Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\) $$f ( n ) = 5 ^ { 2 n } + 3 n - 1$$ is divisible by 9

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