4.01a Mathematical induction: construct proofs

6 Prove by induction that, for all positive integers \(n , 7 ^ { n } + 3 ^ { n - 1 }\) is a multiple of 4 .

2 A sequence \(\left\{ u _ { n } \right\}\) is given by \(u _ { n + 1 } = 4 u _ { n } + 1\) for \(n \geqslant 1\) and \(u _ { 1 } = 3\).

1. Find the values of \(u _ { 2 } , u _ { 3 }\) and \(u _ { 4 }\).
2. Solve the recurrence system (*).
3. 1. Prove by induction that each term of the sequence can be written in the form \(( 10 m + 3 )\) where \(m\) is an integer.
   2. Show that no term of the sequence is a square number.

4

1. Prove by induction that $$2 + ( 3 \times 2 ) + \left( 4 \times 2 ^ { 2 } \right) + \ldots + ( n + 1 ) 2 ^ { n - 1 } = n 2 ^ { n }$$ for all integers \(n \geqslant 1\).
2. Show that $$\sum _ { r = n + 1 } ^ { 2 n } ( r + 1 ) 2 ^ { r - 1 } = n 2 ^ { n } \left( 2 ^ { n + 1 } - 1 \right)$$

5 Prove by induction that for all integers \(n \geqslant 1\) $$\sum _ { r = 1 } ^ { n } \left( r ^ { 2 } + 1 \right) ( r ! ) = n ( n + 1 ) !$$

6 Prove by induction that $$\frac { 2 \times 1 } { 2 \times 3 } + \frac { 2 ^ { 2 } \times 2 } { 3 \times 4 } + \frac { 2 ^ { 3 } \times 3 } { 4 \times 5 } + \ldots + \frac { 2 ^ { n } \times n } { ( n + 1 ) ( n + 2 ) } = \frac { 2 ^ { n + 1 } } { n + 2 } - 1$$ for all integers \(n \geqslant 1\).

6

1. The function f is given by $$\mathrm { f } ( n ) = 15 ^ { n } - 8 ^ { n - 2 }$$ Express $$\mathrm { f } ( n + 1 ) - 8 \mathrm { f } ( n )$$ in the form \(k \times 15 ^ { n }\).
2. Prove by induction that \(15 ^ { n } - 8 ^ { n - 2 }\) is a multiple of 7 for all integers \(n \geqslant 2\).

6

1. Show that $$\left( 1 - \frac { 1 } { ( k + 1 ) ^ { 2 } } \right) \times \frac { k + 1 } { 2 k } = \frac { k + 2 } { 2 ( k + 1 ) }$$
2. Prove by induction that for all integers \(n \geqslant 2\) $$\left( 1 - \frac { 1 } { 2 ^ { 2 } } \right) \left( 1 - \frac { 1 } { 3 ^ { 2 } } \right) \left( 1 - \frac { 1 } { 4 ^ { 2 } } \right) \ldots \left( 1 - \frac { 1 } { n ^ { 2 } } \right) = \frac { n + 1 } { 2 n }$$

5

1. Prove by induction that, if \(n\) is a positive integer, $$( \cos \theta + \mathrm { i } \sin \theta ) ^ { n } = \cos n \theta + \mathrm { i } \sin n \theta$$
2. Hence, given that $$z = \cos \theta + \mathrm { i } \sin \theta$$ show that $$z ^ { n } + \frac { 1 } { z ^ { n } } = 2 \cos n \theta$$
3. Given further that \(z + \frac { 1 } { z } = \sqrt { 2 }\), find the value of $$z ^ { 10 } + \frac { 1 } { z ^ { 10 } }$$

4 The expression \(\mathrm { f } ( n )\) is given by \(\mathrm { f } ( n ) = 2 ^ { 4 n + 3 } + 3 ^ { 3 n + 1 }\).

1. Show that \(\mathrm { f } ( k + 1 ) - 16 \mathrm { f } ( k )\) can be expressed in the form \(A \times 3 ^ { 3 k }\), where \(A\) is an integer.
2. Prove by induction that \(\mathrm { f } ( n )\) is a multiple of 11 for all integers \(n \geqslant 1\).

11

1. Show that, for all positive integers \(r\), $$\frac { 1 } { ( r - 1 ) ! } - \frac { 1 } { r ! } = \frac { r - 1 } { r ! }$$ ⟶
   11
2. Hence, using the method of differences, show that $$\sum _ { r = 1 } ^ { n } \frac { r - 1 } { r ! } = a + \frac { b } { n ! }$$ where \(a\) and \(b\) are integers to be determined.

13 Prove by induction that, for all integers \(n \geq 1\) $$\sum _ { r = 1 } ^ { n } 2 ^ { - r } = 1 - 2 ^ { - n }$$ [4 marks]

11 Prove by induction that, for all integers \(n \geq 1\), $$\left( \mathbf { A B A } ^ { - 1 } \right) ^ { n } = \mathbf { A B } ^ { n } \mathbf { A } ^ { - 1 }$$ where \(\mathbf { A }\) and \(\mathbf { B }\) are square matrices of equal dimensions, and \(\mathbf { A }\) is non-singular.

8

1. The complex number \(z\) is given by \(z = x + i y\) where \(x , y \in \mathbb { R }\) 8
   1. 1. Write down the complex conjugate \(z ^ { * }\) in terms of \(x\) and \(y\) 8
      2. Hence prove that \(z z ^ { * }\) is real for all \(z \in \mathbb { C }\) 8
      3. The complex number \(w\) satisfies the equation $$3 w + 10 \mathrm { i } = 2 w ^ { \star } + 5$$
      8
   2. 1. Find \(w\) 8
   3. (ii) Calculate the value of \(w ^ { 2 } \left( w ^ { * } \right) ^ { 2 }\)

12 Prove by induction that, for all \(n \in \mathbb { N }\), the expression $$5 ^ { n } - 2 ^ { n }$$ is divisible by 3
[0pt] [4 marks]
LL

10

1. Prove that $$6 + 3 \sum _ { r = 1 } ^ { n } ( r + 1 ) ( r + 2 ) = ( n + 1 ) ( n + 2 ) ( n + 3 )$$ [6 marks]
   10
2. Alex substituted a few values of \(n\) into the expression \(( n + 1 ) ( n + 2 ) ( n + 3 )\) and made the statement:
   "For all positive integers n, $$6 + 3 \sum _ { r = 1 } ^ { n } ( r + 1 ) ( r + 2 )$$ is divisible by \(12 . "\) Disprove Alex's statement.
   [0pt] [2 marks]

5 Prove by induction that, for all integers \(n \geq 1\), $$\sum _ { r = 1 } ^ { n } r ^ { 3 } = \left\{ \frac { 1 } { 2 } n ( n + 1 ) \right\} ^ { 2 }$$ [4 marks]

8 In this question you must show detailed reasoning. \(\mathbf { M }\) is the matrix \(\left( \begin{array} { l l } 1 & 6 \\ 0 & 2 \end{array} \right)\).
Prove that \(\mathbf { M } ^ { n } = \left( \begin{array} { c c } 1 & 3 \left( 2 ^ { n + 1 } - 2 \right) \\ 0 & 2 ^ { n } \end{array} \right)\), for any positive integer \(n\). \section*{END OF QUESTION PAPER}

6 Prove by induction that \(4 \times 8 ^ { n } + 66\) is divisible by 14 for all integers \(n \geqslant 0\).

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

4 The first five terms of the Fibonacci sequence, \(\left\{ \mathrm { F } _ { \mathrm { n } } \right\}\), where \(n \geqslant 1\), are \(F _ { 1 } = 1 , F _ { 2 } = 1 , F _ { 3 } = 2 , F _ { 4 } = 3\) and \(F _ { 5 } = 5\).

1. Use the recurrence definition of the Fibonacci sequence, \(\mathrm { F } _ { \mathrm { n } + 1 } = \mathrm { F } _ { \mathrm { n } } + \mathrm { F } _ { \mathrm { n } - 1 }\), to express \(\mathrm { F } _ { \mathrm { n } + 4 }\) in terms of \(\mathrm { F } _ { \mathrm { n } }\) and \(\mathrm { F } _ { \mathrm { n } - 1 }\).
2. Hence prove by induction that \(\mathrm { F } _ { \mathrm { n } }\) is a multiple of 3 when \(n\) is a multiple of 4 .

3 For positive integers \(n\), the sequence of Fibonacci numbers, \(\left\{ \mathrm { F } _ { \mathrm { n } } \right\}\), starts with the terms \(F _ { 1 } = 1 , F _ { 2 } = 1 , F _ { 3 } = 2 , \ldots\) and is given by the recurrence relation \(\mathrm { F } _ { \mathrm { n } } = \mathrm { F } _ { \mathrm { n } - 1 } + \mathrm { F } _ { \mathrm { n } - 2 } ( \mathrm { n } \geqslant 3 )\).

1. Show that \(\mathrm { F } _ { 3 \mathrm { k } + 3 } = 2 \mathrm {~F} _ { 3 \mathrm { k } + 1 } + \mathrm { F } _ { 3 \mathrm { k } }\), where \(k\) is a positive integer.
2. Prove by induction that \(\mathrm { F } _ { 3 n }\) is even for all positive integers \(n\).

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

4 Prove that \(n ! > 2 ^ { 2 n }\) for all integers \(n \geqslant 9\).

1 Let \(\mathbf { A } = \left( \begin{array} { l l } 3 & 0 \\ 1 & 1 \end{array} \right)\).

1. Prove by mathematical induction that, for all positive integers \(n\), $$2 \mathbf { A } ^ { n } = \left( \begin{array} { l l } 2 \times 3 ^ { n } & 0 \\ 3 ^ { n } - 1 & 2 \end{array} \right)$$
2. Find, in terms of \(n\), the inverse of \(\mathbf { A } ^ { n }\).

3 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 { 4 u _ { 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\).
2. Show that \(u _ { n + 1 } > u _ { n }\) for \(n \geqslant 1\).