4.01a Mathematical induction: construct proofs

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 Prove by induction that \(\sum _ { r = 1 } ^ { n } r 3 ^ { r - 1 } = \frac { 1 } { 4 } \left[ 3 ^ { n } ( 2 n - 1 ) + 1 \right]\). Section B (36 marks)

6 Prove by induction that \(1 ^ { 2 } - 2 ^ { 2 } + 3 ^ { 2 } - 4 ^ { 2 } + \ldots + ( - 1 ) ^ { n - 1 } n ^ { 2 } = ( - 1 ) ^ { n - 1 } \frac { n ( n + 1 ) } { 2 }\).

6 Prove by induction that \(3 + 10 + 17 + \ldots + ( 7 n - 4 ) = \frac { 1 } { 2 } n ( 7 n - 1 )\) for all positive integers \(n\). Section B (36 marks)

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 Prove by induction that \(1 + 8 + 27 + \ldots + n ^ { 3 } = \frac { 1 } { 4 } n ^ { 2 } ( n + 1 ) ^ { 2 }\). 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 }\).

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.

6 Prove by induction that \(\frac { 1 } { 1 \times 3 } + \frac { 1 } { 3 \times 5 } + \frac { 1 } { 5 \times 7 } + \ldots + \frac { 1 } { ( 2 n - 1 ) ( 2 n + 1 ) } = \frac { n } { 2 n + 1 }\).

5

1. Show that \(\sum _ { \mathrm { r } = 1 } ^ { \mathrm { n } } ( 2 \mathrm { r } - 1 ) = \mathrm { n } ^ { 2 }\).
2. Show that \(\frac { \sum _ { \mathrm { r } = 1 } ^ { \mathrm { n } } ( 2 \mathrm { r } - 1 ) } { \sum _ { \mathrm { r } = \mathrm { n } + 1 } ^ { 2 \mathrm { n } } ( 2 \mathrm { r } - 1 ) } = \mathrm { k }\), where \(k\) is a constant to be determined.

6 A sequence is defined by \(u _ { 1 } = 3\) and \(u _ { n + 1 } = 3 u _ { n } - 5\). Prove by induction that \(u _ { n } = \frac { 3 ^ { n - 1 } + 5 } { 2 }\). Section B (36 marks)

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

7 Prove by induction that $$\sum _ { r = 1 } ^ { n } \left( 3 r ^ { 5 } + r ^ { 3 } \right) = \frac { 1 } { 2 } n ^ { 3 } ( n + 1 ) ^ { 3 }$$ for all \(n \geqslant 1\). Use this result together with the List of Formulae (MF10) to prove that $$\sum _ { r = 1 } ^ { n } r ^ { 5 } = \frac { 1 } { 12 } n ^ { 2 } ( n + 1 ) ^ { 2 } \mathrm { Q } ( n )$$ where \(\mathrm { Q } ( n )\) is a quadratic function of \(n\) which is to be determined.

7 Let $$I _ { n } = \int _ { 0 } ^ { 1 } t ^ { n } \mathrm { e } ^ { - t } \mathrm {~d} t$$ where \(n \geqslant 0\). Show that, for all \(n \geqslant 1\), $$I _ { n } = n I _ { n - 1 } - \mathrm { e } ^ { - 1 }$$ Hence prove by induction that, for all positive integers \(n\), $$I _ { n } < n ! .$$

5 Let $$I _ { n } = \int _ { 1 } ^ { \mathrm { e } } x ( \ln x ) ^ { n } \mathrm {~d} x$$ where \(n \geqslant 1\). Show that $$I _ { n + 1 } = \frac { 1 } { 2 } \mathrm { e } ^ { 2 } - \frac { 1 } { 2 } ( n + 1 ) I _ { n }$$ Hence prove by induction that, for all positive integers \(n , I _ { n }\) is of the form \(A _ { n } \mathrm { e } ^ { 2 } + B _ { n }\), where \(A _ { n }\) and \(B _ { n }\) are rational numbers.

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

4 It is given that \(\mathrm { f } ( n ) = 3 ^ { 3 n } + 6 ^ { n - 1 }\).

1. Show that \(\mathrm { f } ( n + 1 ) + \mathrm { f } ( n ) = 28 \left( 3 ^ { 3 n } \right) + 7 \left( 6 ^ { n - 1 } \right)\).
2. Hence, or otherwise, prove by mathematical induction that \(\mathrm { f } ( n )\) is divisible by 7 for every positive integer \(n\).

2 Let \(\mathbf { A } = \left( \begin{array} { l l } 2 & 3 \\ 0 & 1 \end{array} \right)\). Prove by mathematical induction that, for every positive integer \(n\), $$\mathbf { A } ^ { n } = \left( \begin{array} { c c } 2 ^ { n } & 3 \left( 2 ^ { n } - 1 \right) \\ 0 & 1 \end{array} \right)$$

2 Prove, by mathematical induction, that, for integers \(n \geqslant 2\), $$4 ^ { n } > 2 ^ { n } + 3 ^ { n }$$

2 For the sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\), it is given that \(u _ { 1 } = 1\) and \(u _ { r + 1 } = \frac { 3 u _ { r } - 2 } { 4 }\) for all \(r\). Prove by mathematical induction that \(u _ { n } = 4 \left( \frac { 3 } { 4 } \right) ^ { n } - 2\), for all positive integers \(n\).

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

3 Prove by mathematical induction that, for every positive integer \(n\), $$\frac { \mathrm { d } ^ { n } } { \mathrm {~d} x ^ { n } } \left( \mathrm { e } ^ { x } \sin x \right) = ( \sqrt { } 2 ) ^ { n } \mathrm { e } ^ { x } \sin \left( x + \frac { 1 } { 4 } n \pi \right)$$

3 Prove by mathematical induction that, for all non-negative integers \(n\), $$11 ^ { 2 n } + 25 ^ { n } + 22$$ is divisible by 24 .

3
- 2
0 \end{array} \right) .$$ Show that \(\{ \mathbf { a } , \mathbf { b } , \mathbf { c } \}\) is a basis for \(\mathbb { R } ^ { 3 }\). Express \(\mathbf { d }\) in terms of \(\mathbf { a } , \mathbf { b }\) and \(\mathbf { c }\). 2 Show that the difference between the squares of consecutive integers is an odd integer. Find the sum to \(n\) terms of the series $$\frac { 3 } { 1 ^ { 2 } \times 2 ^ { 2 } } + \frac { 5 } { 2 ^ { 2 } \times 3 ^ { 2 } } + \frac { 7 } { 3 ^ { 2 } \times 4 ^ { 2 } } + \ldots + \frac { 2 r + 1 } { r ^ { 2 } ( r + 1 ) ^ { 2 } } + \ldots$$ and deduce the sum to infinity of the series. 3 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\).

3 The sequence \(a _ { 1 } , a _ { 2 } , a _ { 3 } , \ldots\) is such that \(a _ { 1 } > 5\) and \(a _ { n + 1 } = \frac { 4 a _ { n } } { 5 } + \frac { 5 } { a _ { n } }\) for every positive integer \(n\).
Prove by mathematical induction that \(a _ { n } > 5\) for every positive integer \(n\). Prove also that \(a _ { n } > a _ { n + 1 }\) for every positive integer \(n\).