4.01a Mathematical induction: construct proofs

4 A sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by $$u _ { n } = 3 ^ { 2 n } - 1$$

1. Write down the value of \(u _ { 1 }\).
2. Show that \(u _ { n + 1 } - u _ { n } = 8 \times 3 ^ { 2 n }\).
3. Hence prove by induction that each term of the sequence is a multiple of 8 .

6 Prove by induction that \(\sum _ { r = 1 } ^ { n } r 2 ^ { r - 1 } = 1 + ( n - 1 ) 2 ^ { n }\).

6 Prove by induction that \(\sum _ { r = 1 } ^ { n } \frac { 1 } { r ( r + 1 ) } = \frac { n } { n + 1 }\).

6 Prove by induction that \(\sum _ { r = 1 } ^ { n } r ^ { 2 } = \frac { 1 } { 6 } n ( n + 1 ) ( 2 n + 1 )\).

9 Matrices \(\mathbf { M }\) and \(\mathbf { N }\) are given by \(\mathbf { M } = \left( \begin{array} { l l } 3 & 2 \\ 0 & 1 \end{array} \right)\) and \(\mathbf { N } = \left( \begin{array} { r r } 1 & - 3 \\ 1 & 4 \end{array} \right)\).

1. Find \(\mathbf { M } ^ { - 1 }\) and \(\mathbf { N } ^ { - 1 }\).
2. Find \(\mathbf { M N }\) and \(( \mathbf { M N } ) ^ { - \mathbf { 1 } }\). Verify that \(( \mathbf { M N } ) ^ { - 1 } = \mathbf { N } ^ { - 1 } \mathbf { M } ^ { - 1 }\).
3. The result \(( \mathbf { P Q } ) ^ { - 1 } = \mathbf { Q } ^ { - 1 } \mathbf { P } ^ { - 1 }\) is true for any two \(2 \times 2\), non-singular matrices \(\mathbf { P }\) and \(\mathbf { Q }\). The first two lines of a proof of this general result are given below. Beginning with these two lines, complete the general proof. $$\begin{aligned} & ( \mathbf { P Q } ) ^ { - 1 } \mathbf { P Q } = \mathbf { I } \\ \Rightarrow & ( \mathbf { P Q } ) ^ { - 1 } \mathbf { P Q Q } \mathbf { Q } ^ { - 1 } = \mathbf { I Q } ^ { - 1 } \end{aligned}$$

6 A sequence is defined by \(a _ { 1 } = 7\) and \(a _ { k + 1 } = 7 a _ { k } - 3\).

1. Calculate the value of the third term, \(a _ { 3 }\).
2. Prove by induction that \(a _ { n } = \frac { \left( 13 \times 7 ^ { n - 1 } \right) + 1 } { 2 }\).

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

10

1. Using the standard formulae for \(\sum _ { r = 1 } ^ { n } r ^ { 2 }\) and \(\sum _ { r = 1 } ^ { n } r ^ { 3 }\), prove that $$\sum _ { r = 1 } ^ { n } r ^ { 2 } ( r + 1 ) = \frac { 1 } { 12 } n ( n + 1 ) ( n + 2 ) ( 3 n + 1 )$$
2. Prove the same result by mathematical induction.

8 It is given that \(I _ { n } = \int _ { 0 } ^ { \frac { 1 } { 4 } \pi } \sec ^ { n } x \mathrm {~d} x\) where \(n\) is a positive integer.

1. By writing \(\sec ^ { n } x = \sec ^ { n - 2 } x \sec ^ { 2 } x\), or otherwise, show that $$( n - 1 ) I _ { n } = ( \sqrt { 2 } ) ^ { n - 2 } + ( n - 2 ) I _ { n - 2 } \text { for } n > 1 .$$
2. Show that \(I _ { 8 } = \frac { 96 } { 35 }\).
3. Prove by induction that \(I _ { 2 n }\) is rational for all values of \(n > 1\). \section*{END OF QUESTION PAPER}

5. \begin{figure}[h] \end{figure} Figure 2 shows a partially completed Venn diagram of sports that a year group of students enjoy,where \(a , b , c , d\) and \(e\) are non-negative integers. The diagram shows how many students enjoy a combination of football( \(F\) ),golf( \(G\) ) and hockey \(( H )\) or none of these sports. There are \(n\) students in the year group.
It is known that
- \(\mathrm { P } ( F ) = \frac { 3 } { 7 }\) - \(\mathrm { P } ( H \mid G ) = \frac { 1 } { 3 }\) -\(F\) is independent of \(H \cap G\)

1. Show that \(\mathrm { P } ( F \cap H \cap G ) = \frac { 1 } { 7 } \mathrm { P } ( G )\)
2. Prove that if two events \(X\) and \(Y\) are independent,then \(X ^ { \prime }\) and \(Y\) are also independent.
3. Hence find the value \(k\) such that \(\mathrm { P } \left( F ^ { \prime } \cap H \cap G \right) = k \mathrm { P } ( G )\)
4. Show that \(c = \frac { 4 } { 3 } a\) Given further that \(\mathrm { P } ( F \mid H ) = \frac { 1 } { 5 }\)
5. find an expression for \(d\) in terms of \(a\) ,and hence deduce the maximum possible value of \(a\) .
6. Determine the possible values of \(n\) .

1. A sequence of non-zero real numbers \(a _ { 1 } , a _ { 2 } , a _ { 3 } , \ldots\) is defined by

$$a _ { n + 1 } = p + \frac { q } { a _ { n } } \quad n \in \mathbb { N }$$ where \(p\) and \(q\) are real numbers with \(q \neq 0\) It is known that

• one of the terms of this sequence is a
• the sequence is periodic
  1. Determine an equation for \(q\), in terms of \(p\) and \(a\), such that the sequence is constant (of period/order one).
  2. Determine the value of \(p\) that is necessary for the sequence to be of period/order 2.
  3. Give an example of a sequence that satisfies the condition in part (b), but is not of period/order 2.
  4. Determine an equation for \(q\), in terms of \(p\) only, such that the sequence has period/order 4.

7. (a) Prove by induction that for \(n \in \mathbb { N }\) $$\sum _ { r = 1 } ^ { n } r ^ { 2 } = \frac { n } { 6 } ( n + 1 ) ( 2 n + 1 )$$ (b) Hence show that $$\sum _ { r = 1 } ^ { n } \left( r ^ { 2 } + 2 \right) = \frac { n } { 6 } \left( a n ^ { 2 } + b n + c \right)$$ where \(a , b\) and \(c\) are integers to be found.
(c) Using your answers to part (b), find the value of $$\sum _ { r = 10 } ^ { 25 } \left( r ^ { 2 } + 2 \right)$$

8. Prove by induction that \(4 ^ { n + 2 } + 5 ^ { 2 n + 1 }\) is divisible by 21 for all positive integers \(n\).

7 It is given that \(u _ { n } = 13 ^ { n } + 6 ^ { n - 1 }\), where \(n\) is a positive integer.

1. Show that \(u _ { n } + u _ { n + 1 } = 14 \times 13 ^ { n } + 7 \times 6 ^ { n - 1 }\).
2. Prove by induction that \(u _ { n }\) is a multiple of 7 .

10 The matrix \(\mathbf { M }\) is given by \(\mathbf { M } = \left( \begin{array} { l l } 1 & 2 \\ 0 & 1 \end{array} \right)\).

1. Find \(\mathbf { M } ^ { 2 }\) and \(\mathbf { M } ^ { 3 }\).
2. Hence suggest a suitable form for the matrix \(\mathbf { M } ^ { n }\).
3. Use induction to prove that your answer to part (ii) is correct.
4. Describe fully the single geometrical transformation represented by \(\mathbf { M } ^ { 10 }\).

3 The sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by \(u _ { 1 } = 2\), and \(u _ { n + 1 } = 2 u _ { n } - 1\) for \(n \geqslant 1\). Prove by induction that \(u _ { n } = 2 ^ { n - 1 } + 1\).

7 The matrix \(\mathbf { M }\) is given by \(\mathbf { M } = \left( \begin{array} { l l } 3 & 0 \\ 2 & 1 \end{array} \right)\).

1. Show that \(\mathbf { M } ^ { 4 } = \left( \begin{array} { l l } 81 & 0 \\ 80 & 1 \end{array} \right)\).
2. Hence suggest a suitable form for the matrix \(\mathbf { M } ^ { n }\), where \(n\) is a positive integer.
3. Use induction to prove that your answer to part (ii) is correct.

10 The sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by \(u _ { 1 } = 3\) and \(u _ { n + 1 } = 3 u _ { n } - 2\).

1. Find \(u _ { 2 }\) and \(u _ { 3 }\) and verify that \(\frac { 1 } { 2 } \left( u _ { 4 } - 1 \right) = 27\).
2. Hence suggest an expression for \(u _ { n }\).
3. Use induction to prove that your answer to part (ii) is correct.

2 Prove by induction that, for \(n \geqslant 1 , \sum _ { r = 1 } ^ { n } \frac { 1 } { r ( r + 1 ) } = \frac { n } { n + 1 }\).

5 Prove by induction that, for \(n \geqslant 1 , \sum _ { r = 1 } ^ { n } 4 \times 3 ^ { r } = 6 \left( 3 ^ { n } - 1 \right)\).

10 The sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by \(u _ { n } = 5 ^ { n } + 2 ^ { n - 1 }\).

1. Find \(u _ { 1 } , u _ { 2 }\) and \(u _ { 3 }\).
2. Hence suggest a positive integer, other than 1 , which divides exactly into every term of the sequence.
3. By considering \(u _ { n + 1 } + u _ { n }\), prove by induction that your suggestion in part (ii) is correct. \section*{OCR}

4 Prove by induction that, for \(n \geqslant 1 , \sum _ { r = 1 } ^ { n } r ( 3 r + 1 ) = n ( n + 1 ) ^ { 2 }\).

5 The sequence \(u _ { 1 } , u _ { 2 } , u _ { 3 } , \ldots\) is defined by $$u _ { 1 } = 5 \text { and } u _ { n + 1 } = 3 u _ { n } + 2 \text { for } n \geqslant 1 \text {. }$$ Prove by induction that \(u _ { n } = 2 \times 3 ^ { n } - 1\).

7 Prove by induction that \(12 + 36 + 108 + \ldots + 4 \times 3 ^ { n } = 6 \left( 3 ^ { n } - 1 \right)\) for all positive integers \(n\).

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