Proof by induction

7 Prove that \(2 ^ { 3 n } - 3 ^ { n }\) is divisible by 5 for all integers \(n \geqslant 1\).

2 Prove, by mathematical induction, that \(5 ^ { n } + 3\) is divisible by 4 for all non-negative integers \(n\).

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

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

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

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

5. Prove that $$\sum _ { r = 1 } ^ { n } 6 \left( r ^ { 2 } - 1 \right) \equiv ( n - 1 ) n ( 2 n + 5 )$$

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

Prove by induction that $$\sum _ { n = 1 } ^ { N } n ^ { 3 } = \frac { 1 } { 4 } N ^ { 2 } ( N + 1 ) ^ { 2 }$$ Use this result, together with the formula for \(\sum _ { n = 1 } ^ { N } n ^ { 2 }\), to show that $$\sum _ { n = 1 } ^ { N } \left( 20 n ^ { 3 } + 36 n ^ { 2 } \right) = N ( N + 1 ) ( N + 3 ) ( 5 N + 2 ) .$$ Let $$S _ { N } = \sum _ { n = 1 } ^ { N } \left( 20 n ^ { 3 } + 36 n ^ { 2 } + \mu n \right)$$ Find the value of the constant \(\mu\) such that \(S _ { N }\) is of the form \(N ^ { 2 } ( N + 1 ) ( a N + b )\), where the constants \(a\) and \(b\) are to be determined. Show that, for this value of \(\mu\), $$5 + \frac { 22 } { N } < N ^ { - 4 } S _ { N } < 5 + \frac { 23 } { N }$$ for all \(N \geqslant 18\).

8 Prove by induction that \(\left( \begin{array} { l l } 1 & 1 \\ 0 & 2 \end{array} \right) ^ { n } = \left( \begin{array} { c c } 1 & 2 ^ { n } - 1 \\ 0 & 2 ^ { n } \end{array} \right)\) for all positive integers \(n\).

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

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

7 Prove by induction that \(\sum _ { r = 1 } ^ { n } 3 ^ { r - 1 } = \frac { 3 ^ { n } - 1 } { 2 }\).

8

1. Prove by mathematical induction that, for \(z \neq 1\) and all positive integers \(n\), $$1 + z + z ^ { 2 } + \ldots + z ^ { n - 1 } = \frac { z ^ { n } - 1 } { z - 1 }$$
2. By letting \(z = \frac { 1 } { 2 } ( \cos \theta + \mathrm { i } \sin \theta )\), use de Moivre's theorem to deduce that $$\sum _ { m = 1 } ^ { \infty } \left( \frac { 1 } { 2 } \right) ^ { m } \sin m \theta = \frac { 2 \sin \theta } { 5 - 4 \cos \theta }$$

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

8
- 2 \end{array} \right) .$$ 6 It is given that \(y = \mathrm { e } ^ { x } u\), where \(u\) is a function of \(x\). The \(r\) th derivatives \(\frac { \mathrm { d } ^ { r } y } { \mathrm {~d} x ^ { r } }\) and \(\frac { \mathrm { d } ^ { r } u } { \mathrm {~d} x ^ { r } }\) are denoted by \(y ^ { ( r ) }\) and \(u ^ { ( r ) }\) respectively. Prove by mathematical induction that, for all positive integers \(n\), $$y ^ { ( n ) } = \mathrm { e } ^ { x } \left( \binom { n } { 0 } u + \binom { n } { 1 } u ^ { ( 1 ) } + \binom { n } { 2 } u ^ { ( 2 ) } + \ldots + \binom { n } { r } u ^ { ( r ) } + \ldots + \binom { n } { n } u ^ { ( n ) } \right)$$ [You may use without proof the result \(\binom { k } { r } + \binom { k } { r - 1 } = \binom { k + 1 } { r }\).]\\ 7 Let $$S _ { N } = \sum _ { r = 1 } ^ { N } ( 3 r + 1 ) ( 3 r + 4 ) \quad \text { and } \quad T _ { N } = \sum _ { r = 1 } ^ { N } \frac { 1 } { ( 3 r + 1 ) ( 3 r + 4 ) } .$$

1. Use standard results from the List of Formulae (MF10) to show that $$S _ { N } = N \left( 3 N ^ { 2 } + 12 N + 13 \right)$$
2. Use the method of differences to show that $$T _ { N } = \frac { 1 } { 12 } - \frac { 1 } { 3 ( 3 N + 4 ) } .$$
3. Deduce that \(\frac { S _ { N } } { T _ { N } }\) is an integer.
4. Find \(\lim _ { N \rightarrow \infty } \frac { S _ { N } } { N ^ { 3 } T _ { N } }\).\\ 8
5. By considering the binomial expansion of \(\left( z + \frac { 1 } { z } \right) ^ { 6 }\), where \(z = \cos \theta + i \sin \theta\), express \(\cos ^ { 6 } \theta\) in the form $$\frac { 1 } { 32 } ( p + q \cos 2 \theta + r \cos 4 \theta + s \cos 6 \theta ) ,$$ where \(p , q , r\) and \(s\) are integers to be determined.
6. Hence find the exact value of $$\int _ { - \frac { 1 } { 2 } \pi } ^ { \frac { 1 } { 2 } \pi } \cos ^ { 6 } \left( \frac { 1 } { 2 } x \right) \mathrm { d } x$$

2 Prove by mathematical induction that, for all positive integers \(n\), $$\frac { \mathrm { d } ^ { n } } { \mathrm {~d} x ^ { n } } \left( \tan ^ { - 1 } x \right) = P _ { n } ( x ) \left( 1 + x ^ { 2 } \right) ^ { - n } ,$$ where \(P _ { n } ( x )\) is a polynomial of degree \(n - 1\). \includegraphics[max width=\textwidth, alt={}, center]{99ac7fe2-184b-4a72-89f6-03fe4b2af138-05_2726_35_97_20}

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

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

9 Use induction to prove that $$\sum _ { n = 1 } ^ { N } \frac { 4 n + 1 } { n ( n + 1 ) ( 2 n - 1 ) ( 2 n + 1 ) } = 1 - \frac { 1 } { ( N + 1 ) ( 2 N + 1 ) }$$ Show that $$\sum _ { n = N + 1 } ^ { 2 N } \frac { 4 n + 1 } { n ( n + 1 ) ( 2 n - 1 ) ( 2 n + 1 ) } < \frac { 3 } { 8 N ^ { 2 } }$$

8 Prove that \(n ! > 2 ^ { n }\) for \(n \geq 4\).

2 Prove, by mathematical induction, that, for integers \(n \geqslant 2\), $$4 ^ { n } > 2 ^ { n } + 3 ^ { 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\).

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.

3 It is given that, for \(n = 0,1,2,3 , \ldots\), $$a _ { n } = 17 ^ { 2 n } + 3 ( 9 ) ^ { n } + 20$$ Simplify \(a _ { n + 1 } - a _ { n }\), and hence prove by induction that \(a _ { n }\) is divisible by 24 for all \(n \geqslant 0\).

8

1. Use standard series formulae to show that $$\sum _ { r = 1 } ^ { n } [ r ( r - 1 ) - 1 ] = \frac { 1 } { 3 } n ( n + 2 ) ( n - 2 )$$
2. Prove (*) by mathematical induction.

3 Prove by mathematical induction that, for all integers \(n \geqslant 1 , n ^ { 5 } - n\) is divisible by 5 .

7 Prove by induction that the sum of the cubes of three consecutive positive integers is divisible by 9 .

9 Prove by mathematical induction that, for every positive integer \(n\), $$( \cos \theta + i \sin \theta ) ^ { n } = \cos n \theta + i \sin n \theta$$ Express \(\sin ^ { 5 } \theta\) in the form \(p \sin 5 \theta + q \sin 3 \theta + r \sin \theta\), where \(p , q\) and \(r\) are rational numbers to be determined.

3 Prove, by mathematical induction, that \(\sum _ { r = 1 } ^ { n } r \ln \left( \frac { r + 1 } { r } \right) = \ln \left( \frac { ( n + 1 ) ^ { n } } { n ! } \right)\) for all positive integers \(n\). [6]

8. The points \(P , Q\) and \(R\) have coordinates \(( - 5,2 ) , ( - 3,8 )\) and \(( 9,4 )\) respectively.

1. Show that \(\angle P Q R = 90 ^ { \circ }\). Given that \(P , Q\) and \(R\) all lie on circle \(C\),
2. find the coordinates of the centre of \(C\),
3. show that the equation of \(C\) can be written in the form $$x ^ { 2 } + y ^ { 2 } + a x + b y = k$$ where \(a , b\) and \(k\) are integers to be found.
   [0pt] [BLANK PAGE]
   [0pt] [BLANK PAGE]