4.01a Mathematical induction: construct proofs

11

1. At all points \(( x , y )\) on the curve \(C , \frac { \mathrm {~d} y } { \mathrm {~d} x } + x y = 0\).
   1. Prove by induction that, for all integers \(n \geqslant 1\), $$\frac { \mathrm { d } ^ { n + 1 } y } { \mathrm {~d} x ^ { n + 1 } } + x \frac { \mathrm {~d} ^ { n } y } { \mathrm {~d} x ^ { n } } + n \frac { \mathrm {~d} ^ { n - 1 } y } { \mathrm {~d} x ^ { n - 1 } } = 0$$ where \(\frac { \mathrm { d } ^ { 0 } y } { \mathrm {~d} x ^ { 0 } } = y\).
   2. Given that \(y = 1\) when \(x = 0\), determine the Maclaurin expansion of \(y\) in ascending powers of \(x\), up to and including the term in \(x ^ { 6 }\).
   3. Solve the differential equation \(\frac { \mathrm { d } y } { \mathrm {~d} x } + x y = 0\) given that \(y = 1\) when \(x = 0\).
   4. Given that \(Z \sim \mathrm {~N} ( 0,1 )\), use your answers to parts (i) and (ii) to find an approximation, to 4 decimal places, to the probability \(\mathrm { P } ( Z \leqslant 1 )\).
      [0pt] [Note that the probability density function of the standard normal distribution is \(\mathrm { f } ( z ) = \frac { 1 } { \sqrt { 2 \pi } } \mathrm { e } ^ { - \frac { 1 } { 2 } z ^ { 2 } }\).]

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.

12 Given \(y = x \mathrm { e } ^ { 2 x }\),

1. find the first four derivatives of \(y\) with respect to \(x\),
2. conjecture an expression for \(\frac { \mathrm { d } ^ { n } y } { \mathrm {~d} x ^ { n } }\) in the form \(( a x + b ) \mathrm { e } ^ { 2 x }\), where \(a\) and \(b\) are functions of \(n\),
3. prove by induction that your result holds for all positive integers \(n\).

7 Let \(\mathrm { f } ( n ) = 11 ^ { 2 n - 1 } + 7 \times 4 ^ { n }\). Prove by induction that \(\mathrm { f } ( n )\) is divisible by 13 for all positive integers \(n\).

11

1. The sequence of Fibonacci Numbers \(\left\{ F _ { n } \right\}\) is given by $$F _ { 1 } = 1 , \quad F _ { 2 } = 1 \quad \text { and } \quad F _ { n + 1 } = F _ { n } + F _ { n - 1 } \text { for } n \geqslant 2 .$$ Write down the values of \(F _ { 3 }\) to \(F _ { 6 }\).
2. The sequence of functions \(\left\{ \mathrm { p } _ { n } ( x ) \right\}\) is given by $$\mathrm { p } _ { 1 } ( x ) = x + 1 \quad \text { and } \quad \mathrm { p } _ { n + 1 } ( x ) = 1 + \frac { 1 } { \mathrm { p } _ { n } ( x ) } \text { for } n \geqslant 1$$
   1. Find \(\mathrm { p } _ { 2 } ( x )\) and \(\mathrm { p } _ { 3 } ( x )\), giving each answer as a single algebraic fraction, and show that \(\mathrm { p } _ { 4 } ( x ) = \frac { 3 x + 5 } { 2 x + 3 }\).
   2. Conjecture an expression for \(\mathrm { p } _ { n } ( x )\) as a single algebraic fraction involving Fibonacci numbers, and prove it by induction for all integers \(n \geqslant 2\).

13 Define the repunit number, \(R _ { n }\), to be the positive integer which consists of a string of \(n 1 \mathrm {~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 7s.

5 Use induction to prove that \(\sum _ { r = 1 } ^ { n } \left( \frac { 2 } { 4 r - 1 } \right) \left( \frac { 2 } { 4 r + 3 } \right) = \frac { 1 } { 3 } - \frac { 1 } { 4 n + 3 }\) for all positive integers \(n\).

12 For each positive integer \(n\), the function \(\mathrm { F } _ { n }\) is defined for all real angles \(\theta\) by $$\mathrm { F } _ { n } ( \theta ) = c ^ { 2 n } + s ^ { 2 n }$$ where \(c = \cos \theta\) and \(s = \sin \theta\).

1. Prove the identity $$\mathrm { F } _ { n + 2 } ( \theta ) - \frac { 1 } { 4 } \sin ^ { 2 } 2 \theta \times \mathrm { F } _ { n + 1 } ( \theta ) \equiv \mathrm { F } _ { n + 3 } ( \theta )$$ Let \(z\) denote the complex number \(c + \mathrm { i } s\).
2. Using de Moivre's theorem,
   1. express \(z + z ^ { - 1 }\) and \(z - z ^ { - 1 }\) in terms of \(c\) and \(s\) respectively,
   2. prove the identity \(8 \left( c ^ { 6 } + s ^ { 6 } \right) \equiv 3 \cos 4 \theta + 5\) and deduce that $$c ^ { 6 } + s ^ { 6 } \equiv \cos ^ { 2 } 2 \theta + \frac { 1 } { 4 } \sin ^ { 2 } 2 \theta$$
   3. Prove by induction that, for all positive integers \(n\), $$c ^ { 2 n + 4 } + s ^ { 2 n + 4 } \leqslant \cos ^ { 2 } 2 \theta + \frac { 1 } { 2 ^ { n + 1 } } \sin ^ { 2 } 2 \theta$$ [You are given that the range of the function \(\mathrm { F } _ { n }\) is \(\frac { 1 } { 2 ^ { n - 1 } } \leqslant \mathrm {~F} _ { n } ( \theta ) \leqslant 1\).] {www.cie.org.uk} after the live examination series. }

12

1. The sequence \(\left\{ u _ { n } \right\}\) is defined for all integers \(n \geq 0\) by $$u _ { 0 } = 1 \quad \text { and } \quad u _ { n } = n u _ { n - 1 } + 1 , \quad n \geq 1 .$$ Prove by induction that \(u _ { n } = n ! \sum _ { r = 0 } ^ { n } \frac { 1 } { r ! }\).
2. (a) Given that \(I _ { n } = \int _ { 0 } ^ { 1 } x ^ { n } \mathrm { e } ^ { - x } \mathrm {~d} x\) for \(n \geq 0\), show that, for \(n \geq 1\), $$I _ { n } = n I _ { n - 1 } - \frac { 1 } { \mathrm { e } }$$ (b) Evaluate \(I _ { 0 }\) exactly and deduce the value of \(I _ { 1 }\).
   (c) Show that \(I _ { n } = n ! - \frac { u _ { n } } { \mathrm { e } }\) for all integers \(n \geq 1\).

13 Let \(I _ { n } = \int _ { 1 } ^ { \mathrm { e } } ( \ln x ) ^ { n } \mathrm {~d} x\), where \(n\) is a positive integer.

1. By considering \(\frac { \mathrm { d } } { \mathrm { d } x } \left( x ( \ln x ) ^ { n } \right)\), or otherwise, show that \(I _ { n } = \mathrm { e } - n I _ { n - 1 }\).
2. Let \(J _ { n } = \frac { I _ { n } } { n ! }\). Prove by induction that $$\sum _ { r = 2 } ^ { n } \frac { ( - 1 ) ^ { r } } { r ! } = \frac { 1 } { \mathrm { e } } \left( 1 + ( - 1 ) ^ { n } J _ { n } \right)$$ for all positive integers \(n \geqslant 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\). [6]

Given that \(y = x \sin x\), find \(\frac{d^2y}{dx^2}\) and \(\frac{d^4y}{dx^4}\), simplifying your results as far as possible, and show that $$\frac{d^6y}{dx^6} = -x \sin x + 6 \cos x.$$ [3] Use induction to establish an expression for \(\frac{d^{2n}y}{dx^{2n}}\), where \(n\) is a positive integer. [5]

The sequence \(u_1, u_2, u_3, \ldots\) is such that \(u_1 = 1\) and $$u_{n+1} = -1 + \sqrt{(u_n + 7)}.$$

1. Prove by induction that \(u_n < 2\) for all \(n \geqslant 1\). [4]
2. Show that if \(u_n = 2 - \varepsilon\), where \(\varepsilon\) is small, then $$u_{n+1} \approx 2 - \frac{1}{6}\varepsilon.$$ [2]

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]

The sequence of positive numbers \(u_1\), \(u_2\), \(u_3\), \(\ldots\) is such that \(u_1 < 3\) and, for \(n \geqslant 1\), $$u_{n+1} = \frac{4u_n + 9}{u_n + 4}.$$

1. By considering \(3 - u_{n+1}\), or otherwise, prove by mathematical induction that \(u_n < 3\) for all positive integers \(n\). [5]
2. Show that \(u_{n+1} > u_n\) for \(n \geqslant 1\). [3]

It is given that \(y = 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)} = 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].$$ [8] [You may use without proof the result \(\binom{k}{r} + \binom{k}{r-1} = \binom{k+1}{r}\).]

It is given that \(y = \ln(ax + 1)\), where \(a\) is a positive constant. Prove by mathematical induction that, for every positive integer \(n\), $$\frac{d^n y}{dx^n} = (-1)^{n-1} \frac{(n-1)!a^n}{(ax+1)^n}.$$ [6]

It is given that \(y = \ln(ax + 1)\), where \(a\) is a positive constant. Prove by mathematical induction that, for every positive integer \(n\), $$\frac{d^n y}{dx^n} = (-1)^{n-1} \frac{(n-1)! a^n}{(ax+1)^n}.$$ [6]

Prove by induction that, for \(n \in \mathbb{Z}^+\), $$\sum_{r=1}^n \frac{1}{r(r+1)} = \frac{n}{n+1}$$ [5]

A series of positive integers \(u_1, u_2, u_3, \ldots\) is defined by $$u_1 = 6 \text{ and } u_{n+1} = 6u_n - 5, \text{ for } n \geq 1.$$ Prove by induction that \(u_n = 5 \times 6^{n-1} + 1\), for \(n \geq 1\). [5]

For \(n \in \mathbb{Z}^+\) prove that

1. \(2^{3n + 2} + 5^{n + 1}\) is divisible by 3, [9]
2. \(\begin{pmatrix} -2 & -1 \\ 9 & 4 \end{pmatrix}^n = \begin{pmatrix} 1-3n & -n \\ 9n & 3n+1 \end{pmatrix}\). [7]

$$f(n) = (2n + 1)7^n - 1.$$ Prove by induction that, for all positive integers \(n\), \(f(n)\) is divisible by 4. [6]