Proof by induction

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

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

13 Define the repunit number, \(R _ { n }\), to be the positive integer which consists of a string of \(n 1\) 's. Thus, $$R _ { 1 } = 1 , \quad R _ { 2 } = 11 , \quad R _ { 3 } = 111 , \quad \ldots , \quad R _ { 7 } = 1111111 , \quad \ldots , \text { etc. }$$ Use induction to prove that, for all integers \(n \geqslant 5\), the number $$13579 \times R _ { n }$$ contains a string of ( \(n - 4\) ) consecutive 7's.

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

Prove by induction that, for \(n \geq 1\), \(\sum_{r=1}^n r(3r + 1) = n(n + 1)^2\). [5]

Prove by induction that, for all positive integers \(n\), $$\sum_{r=1}^{n}(2r-1)^2 = \frac{1}{3}n(4n^2-1)$$ [6]

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

Prove that for all \(n \in \mathbb{N}\) $$\begin{pmatrix} 3 & 4i \\ i & -1 \end{pmatrix}^n = \begin{pmatrix} 2n+1 & 4ni \\ ni & 1-2n \end{pmatrix}$$ [6]

The matrix \(\mathbf{A}\) is given by \(\mathbf{A} = \begin{pmatrix} 2 & 0 \\ 0 & 1 \end{pmatrix}\).

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

In this question you must show detailed reasoning. M is the matrix \(\begin{pmatrix} 1 & 6 \\ 0 & 2 \end{pmatrix}\). Prove that \(\mathbf{M}^n = \begin{pmatrix} 1 & 3(2^{n+1} - 2) \\ 0 & 2^n \end{pmatrix}\), for any positive integer \(n\). [6]

Given that \(a\) is a constant, prove by mathematical induction that, for every positive integer \(n\), $$\frac{\mathrm{d}^n}{\mathrm{d}x^n}(xe^{ax}) = na^{n-1}e^{ax} + a^n xe^{ax}.$$ [6]

Given that \(a\) is a constant, prove by mathematical induction that, for every positive integer \(n\), $$\frac{\mathrm{d}^n}{\mathrm{d}x^n}(xe^{ax}) = na^{n-1}e^{ax} + a^n xe^{ax}.$$ [6]

3

1. Show that \(\frac { \mathrm { d } ^ { n + 1 } } { \mathrm {~d} x ^ { n + 1 } } \left( x ^ { n + 1 } \ln x \right) = \frac { \mathrm { d } ^ { n } } { \mathrm {~d} x ^ { n } } \left( x ^ { n } + ( n + 1 ) x ^ { n } \ln x \right)\).
2. Prove by mathematical induction that, for all positive integers \(n\), $$\frac { \mathrm { d } ^ { n } } { \mathrm {~d} x ^ { n } } \left( x ^ { n } \ln x \right) = n ! \left( \ln x + 1 + \frac { 1 } { 2 } + \ldots + \frac { 1 } { n } \right)$$

Prove by induction that \(\sum_{r=1}^{n} 3^{r-1} = \frac{3^n - 1}{2}\). [6]

5 Prove by induction that, for all positive integers \(n , \sum _ { r = 1 } ^ { n } \frac { 1 } { 3 ^ { r } } = \frac { 1 } { 2 } \left( 1 - \frac { 1 } { 3 ^ { n } } \right)\).

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

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

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

Prove that \(n! > 2^n\) for \(n \geq 4\). [5]

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

3 The sequence \(x _ { 1 } , x _ { 2 } , x _ { 3 } , \ldots\) is such that \(x _ { 1 } = 3\) and $$x _ { n + 1 } = \frac { 2 x _ { n } ^ { 2 } + 4 x _ { n } - 2 } { 2 x _ { n } + 3 }$$ for \(n = 1,2,3 , \ldots\). Prove by induction that \(x _ { n } > 2\) for all \(n\).

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.

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.

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

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]
   [0pt]