4.01a Mathematical induction: construct proofs

3 Prove by mathematical induction that, for all positive integers \(n , 10 ^ { n } + 3 \times 4 ^ { n + 2 } + 5\) is divisible by 9 .

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

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]

2 It is given that \(\mathrm { f } ( n ) = 2 ^ { 3 n } + 8 ^ { n - 1 }\). By simplifying \(\mathrm { f } ( k ) + \mathrm { f } ( k + 1 )\), or otherwise, prove by mathematical induction that \(\mathrm { f } ( n )\) is divisible by 9 for every positive integer \(n\).

9 For the sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\), it is given that \(u _ { 1 } = 8\) and $$u _ { r + 1 } = \frac { 5 u _ { r } - 3 } { 4 }$$ for all \(r\).

1. Prove by mathematical induction that $$u _ { n } = 4 \left( \frac { 5 } { 4 } \right) ^ { n } + 3$$ for all positive integers \(n\).
2. Deduce the set of values of \(x\) for which the infinite series $$\left( u _ { 1 } - 3 \right) x + \left( u _ { 2 } - 3 \right) x ^ { 2 } + \ldots + \left( u _ { r } - 3 \right) x ^ { r } + \ldots$$ is convergent.
3. Use the result given in part (i) to find surds \(a\) and \(b\) such that $$\sum _ { n = 1 } ^ { N } \ln \left( u _ { n } - 3 \right) = N ^ { 2 } \ln a + N \ln b .$$

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

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

9 A cubic equation \(x ^ { 3 } + b x ^ { 2 } + c x + d = 0\) has real roots \(\alpha , \beta\) and \(\gamma\) such that $$\begin{aligned} \frac { 1 } { \alpha } + \frac { 1 } { \beta } + \frac { 1 } { \gamma } & = - \frac { 5 } { 12 } \\ \alpha \beta \gamma & = - 12 \\ \alpha ^ { 3 } + \beta ^ { 3 } + \gamma ^ { 3 } & = 90 \end{aligned}$$

1. Find the values of \(c\) and \(d\).
2. Express \(\alpha ^ { 2 } + \beta ^ { 2 } + \gamma ^ { 2 }\) in terms of \(b\).
3. Show that \(b ^ { 3 } - 15 b + 126 = 0\).
4. Given that \(3 + \mathrm { i } \sqrt { } ( 12 )\) is a root of \(y ^ { 3 } - 15 y + 126 = 0\), deduce the value of \(b\).

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 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) ^ { \lambda }$$ where \(\lambda\) is a constant greater than 1 . Prove by mathematical induction that, for \(n \geqslant 2\), $$a _ { n } \geqslant 2 ^ { \mathrm { g } ( n ) }$$ where \(g ( n ) = \lambda ^ { n - 1 }\). Prove also that, for \(n \geqslant 2 , \frac { a _ { n + 1 } } { a _ { n } } > 2 ^ { ( \lambda - 1 ) \mathrm { g } ( n ) }\).

3 Verify that if $$v _ { n } = n ( n + 1 ) ( n + 2 ) \ldots ( n + m )$$ then $$v _ { n + 1 } - v _ { n } = ( m + 1 ) ( n + 1 ) ( n + 2 ) \ldots ( n + m ) .$$ Given now that $$u _ { n } = ( n + 1 ) ( n + 2 ) \ldots ( n + m ) ,$$ find \(\sum _ { n = 1 } ^ { N } u _ { n }\) in terms of \(m\) and \(N\).

4 Prove by mathematical induction that, for all positive integers \(n , 10 ^ { 3 n } + 13 ^ { n + 1 }\) is divisible by 7 .

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

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

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

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

5 Let \(I _ { n }\) denote \(\int _ { 0 } ^ { \infty } x ^ { n } \mathrm { e } ^ { - 2 x } \mathrm {~d} x\). Show that \(I _ { n } = \frac { 1 } { 2 } n I _ { n - 1 }\), for \(n \geqslant 1\). Prove by mathematical induction that, for all positive integers \(n , I _ { n } = \frac { n ! } { 2 ^ { n + 1 } }\).

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 It is given that \(u _ { r } = r \times r !\) for \(r = 1,2,3 , \ldots\). Let \(S _ { n } = u _ { 1 } + u _ { 2 } + u _ { 3 } + \ldots + u _ { n }\). Write down the values of $$2 ! - S _ { 1 } , \quad 3 ! - S _ { 2 } , \quad 4 ! - S _ { 3 } , \quad 5 ! - S _ { 4 }$$ Conjecture a formula for \(S _ { n }\). Prove, by mathematical induction, a formula for \(S _ { n }\), for all positive integers \(n\).

4 Using factorials, show that \(\binom { n } { r - 1 } + \binom { n } { r } = \binom { n + 1 } { r }\). Hence prove by mathematical induction that $$( a + x ) ^ { n } = \binom { n } { 0 } a ^ { n } + \binom { n } { 1 } a ^ { n - 1 } x + \ldots + \binom { n } { r } a ^ { n - r } x ^ { r } + \ldots + \binom { n } { n } x ^ { n }$$ for every positive integer \(n\).

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

2 It is given that \(y = \ln ( a x + 1 )\), where \(a\) is a positive constant. Prove by mathematical induction that, for every positive integer \(n\), $$\frac { \mathrm { d } ^ { n } y } { \mathrm {~d} x ^ { n } } = ( - 1 ) ^ { n - 1 } \frac { ( n - 1 ) ! a ^ { n } } { ( a x + 1 ) ^ { n } }$$

3 Given that \(a\) is a constant, prove by mathematical induction that, for every positive integer \(n\), $$\frac { \mathrm { d } ^ { n } } { \mathrm {~d} x ^ { n } } \left( x \mathrm { e } ^ { a x } \right) = n a ^ { n - 1 } \mathrm { e } ^ { a x } + a ^ { n } x \mathrm { e } ^ { a x }$$

3 Prove by mathematical induction that, for all positive integers \(n , \sum _ { r = 1 } ^ { n } \frac { 1 } { ( 2 r ) ^ { 2 } - 1 } = \frac { n } { 2 n + 1 }\). State the value of \(\sum _ { r = 1 } ^ { \infty } \frac { 1 } { ( 2 r ) ^ { 2 } - 1 }\).

3 Prove by induction that, for all \(n \geqslant 1\), $$\frac { \mathrm { d } ^ { n } } { \mathrm {~d} x ^ { n } } \left( \mathrm { e } ^ { x ^ { 2 } } \right) = \mathrm { P } _ { n } ( x ) \mathrm { e } ^ { x ^ { 2 } } ,$$ where \(\mathrm { P } _ { n } ( x )\) is a polynomial in \(x\) of degree \(n\) with the coefficient of \(x ^ { n }\) equal to \(2 ^ { n }\).