4.01a Mathematical induction: construct proofs

1. Prove by mathematical induction that, for \(n \in \mathbb { N }\)

$$\sum _ { r = 1 } ^ { n } \frac { 1 } { ( 2 r - 1 ) ( 2 r + 1 ) } = \frac { n } { 2 n + 1 }$$

1. Prove by induction that, for \(n \in \mathbb { Z } ^ { + }\)

$$f ( n ) = 2 ^ { n + 2 } + 3 ^ { 2 n + 1 }$$ is divisible by 7

1. Prove by mathematical induction that, for \(n \in \mathbb { N }\)

$$\left( \begin{array} { l l } - 5 & 9 \\ - 4 & 7 \end{array} \right) ^ { n } = \left( \begin{array} { c c } 1 - 6 n & 9 n \\ - 4 n & 1 + 6 n \end{array} \right)$$

3 A tree at the bottom of a garden needs to be reduced in height. The tree is known to increase in height by 15 centimetres each year. On the first day of every year, the height is measured and the tree is immediately trimmed by \(3 \%\) of this height. When the tree is measured, before trimming on the first day of year 1 , the height is 6 metres.
Let \(H _ { n }\) be the height of the tree immediately before trimming on the first day of year \(n\).

1. Explain, in the context of the problem, why the height of the tree may be modelled by the recurrence relation $$H _ { n + 1 } = 0.97 H _ { n } + 0.15 , \quad H _ { 1 } = 6 , \quad n \in \mathbb { Z } ^ { + }$$
2. Prove by induction that \(H _ { n } = 0.97 ^ { n - 1 } + 5 , \quad n \geqslant 1\)
3. Explain what will happen to the height of the tree immediately before trimming in the long term.
4. By what fixed percentage should the tree be trimmed each year if the height of the tree immediately before trimming is to be 4 metres in the long term?

1. Sam borrows \(\pounds 10000\) from a bank to pay for an extension to his house.

The bank charges \(5 \%\) annual interest on the portion of the loan yet to be repaid. Immediately after the interest has been added at the end of each year and before the start of the next year, Sam pays the bank a fixed amount, \(\pounds F\). Given that \(\pounds A _ { n }\) (where \(A _ { n } \geqslant 0\) ) is the amount owed at the start of year \(n\),

1. write down an expression for \(A _ { n + 1 }\) in terms of \(A _ { n }\) and \(F\),
2. prove, by induction that, for \(n \geqslant 1\) $$A _ { n } = ( 10000 - 20 F ) 1.05 ^ { n - 1 } + 20 F$$
3. Find the smallest value of \(F\) for which Sam can repay all of the loan by the start of year 16 .

1. A population of deer on a large estate is assumed to increase by \(10 \%\) during each year due to natural causes.

The population is controlled by removing a constant number, \(Q\), of the deer from the estate at the end of each year. At the start of the first year there are 5000 deer on the estate.
Let \(P _ { n }\) be the population of deer at the end of year \(n\).

1. Explain, in the context of the problem, the reason that the deer population is modelled by the recurrence relation $$P _ { n } = 1.1 P _ { n - 1 } - Q , \quad P _ { 0 } = 5000 , \quad n \in \mathbb { Z } ^ { + }$$
2. Prove by induction that \(P _ { n } = ( 1.1 ) ^ { n } ( 5000 - 10 Q ) + 10 Q , \quad n \geqslant 0\)
3. Explain how the long term behaviour of this population varies for different values of \(Q\).

1. Prove that, for \(n \in \mathbb { Z } , n \geqslant 0\)

$$\sum _ { r = 0 } ^ { n } \frac { 1 } { ( r + 1 ) ( r + 2 ) ( r + 3 ) } = \frac { ( n + a ) ( n + b ) } { c ( n + 2 ) ( n + 3 ) }$$ where \(a\), \(b\) and \(c\) are integers to be found.

1. Prove by induction that for all positive integers \(n\)

$$f ( n ) = 3 ^ { 2 n + 4 } - 2 ^ { 2 n }$$ is divisible by 5
(6)

1. Prove by induction that for \(n \in \mathbb { N }\)

$$\left( \begin{array} { c c } 1 & - 2 \\ 0 & 1 \end{array} \right) ^ { n } = \left( \begin{array} { c c } 1 & - 2 n \\ 0 & 1 \end{array} \right)$$

1. Prove by induction that, for all positive integers \(n\),

$$\sum _ { r = 1 } ^ { n } ( 2 r - 1 ) ^ { 2 } = \frac { 1 } { 3 } n \left( 4 n ^ { 2 } - 1 \right)$$

1. Prove by induction that for all positive integers \(n\),

$$f ( n ) = 2 ^ { 3 n + 1 } + 3 \left( 5 ^ { 2 n + 1 } \right)$$ is divisible by 17

\(\mathbf { M } = \left( \begin{array} { l l } 3 & a \\ 0 & 1 \end{array} \right) \quad\) where \(a\) is a constant

1. Prove by mathematical induction that, for \(n \in \mathbb { N }\) $$\mathbf { M } ^ { n } = \left( \begin{array} { c c } 3 ^ { n } & \frac { a } { 2 } \left( 3 ^ { n } - 1 \right) \\ 0 & 1 \end{array} \right)$$ Triangle \(T\) has vertices \(A , B\) and \(C\).
   Triangle \(T\) is transformed to triangle \(T ^ { \prime }\) by the transformation represented by \(\mathbf { M } ^ { n }\) where \(n \in \mathbb { N }\) Given that
   • triangle \(T\) has an area of \(5 \mathrm {~cm} ^ { 2 }\)
   • triangle \(T ^ { \prime }\) has an area of \(1215 \mathrm {~cm} ^ { 2 }\)
   • vertex \(A ( 2 , - 2 )\) is transformed to vertex \(A ^ { \prime } ( 123 , - 2 )\)
   • determine
     1. the value of \(n\)
     2. the value of \(a\)

1. Given that

$$y = \mathrm { e } ^ { 2 x } \sinh x$$ prove by induction that for \(n \in \mathbb { N }\) $$\frac { \mathrm { d } ^ { n } y } { \mathrm {~d} x ^ { n } } = \mathrm { e } ^ { 2 x } \left( \frac { 3 ^ { n } + 1 } { 2 } \sinh x + \frac { 3 ^ { n } - 1 } { 2 } \cosh x \right)$$

1. (i)

$$\mathbf { M } = \left( \begin{array} { c c c } 2 & a & 4 \\ 1 & - 1 & - 1 \\ - 1 & 2 & - 1 \end{array} \right)$$ where \(a\) is a constant.

1. For which values of \(a\) does the matrix \(\mathbf { M }\) have an inverse? Given that \(\mathbf { M }\) is non-singular,
2. find \(\mathbf { M } ^ { - 1 }\) in terms of \(a\) (ii) Prove by induction that for all positive integers \(n\), $$\left( \begin{array} { l l } 3 & 0 \\ 6 & 1 \end{array} \right) ^ { n } = \left( \begin{array} { c c } 3 ^ { n } & 0 \\ 3 \left( 3 ^ { n } - 1 \right) & 1 \end{array} \right)$$

1. A recurrence system is defined by

$$\begin{aligned} u _ { n + 2 } & = 9 ( n + 1 ) ^ { 2 } u _ { n } - 3 u _ { n + 1 } \quad n \geqslant 1 \\ u _ { 1 } & = - 3 , u _ { 2 } = 18 \end{aligned}$$ Prove by induction that, for \(n \in \mathbb { N }\), $$u _ { n } = ( - 3 ) ^ { n } n !$$

3. \begin{figure}[h] \end{figure} There are three lily pads on a pond. A frog hops repeatedly from one lily pad to another.
The frog starts on lily pad A, as shown in Figure 1.
In a model, the frog hops from its position on one lily pad to either of the other two lily pads with equal probability. Let \(p _ { n }\) be the probability that the frog is on lily pad A after \(n\) hops.

1. Explain, with reference to the model, why \(p _ { 1 } = 0\) The probability \(p _ { n }\) satisfies the recurrence relation $$p _ { n + 1 } = \frac { 1 } { 2 } \left( 1 - p _ { n } \right) \quad n \geqslant 1 \quad \text { where } p _ { 1 } = 0$$
2. Prove by induction that, for \(n \geqslant 1\) $$p _ { n } = \frac { 2 } { 3 } \left( - \frac { 1 } { 2 } \right) ^ { n } + \frac { 1 } { 3 }$$
3. Use the result in part (b) to explain why, in the long term, the probability that the frog is on lily pad A is \(\frac { 1 } { 3 }\)

1. In a model for the number of subscribers to a new social media channel it is assumed that

• each week \(20 \%\) of the subscribers at the start of the week cancel their subscriptions
• between the start and end of week \(n\) the channel gains \(20 n\) new subscribers

Given that at the end of week 1 there were 25 subscribers,

1. explain why the number of subscribers at the end of week \(n , U _ { n }\), is modelled by the recurrence relation $$U _ { 1 } = 25 \quad U _ { n + 1 } = 0.8 U _ { n } + 20 ( n + 1 ) \quad n = 1,2,3 , \ldots$$
2. Prove by induction that for \(n \geqslant 1\) $$U _ { n } = 325 \left( \frac { 4 } { 5 } \right) ^ { n - 1 } + 100 n - 400$$ Given that 6 months after starting the channel there were approximately 1800 subscribers,
3. evaluate the model in the light of this information.

5 Given that \(n\) is a positive integer greater than 2 , prove that

1. \(\quad 10201 _ { n }\) is a square number.
2. \(\quad 1221 _ { n }\) is a composite number.

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

8 In this question you must show detailed reasoning. A sequence of vectors \(\mathbf { a } _ { 1 } , \mathbf { a } _ { 2 } , \mathbf { a } _ { 3 } , \ldots\) is defined by

• \(\mathbf { a } _ { 1 } = \left( \begin{array} { l } 1 \\ 1 \\ 1 \end{array} \right)\)
• \(\quad \mathbf { a } _ { n + 1 } = \left( \mathbf { a } _ { n } \times \mathbf { b } \right) \times \mathbf { b }\), for integers \(n \geqslant 1\), where \(\mathbf { b }\) is the vector \(\frac { 1 } { 4 } \left( \begin{array} { c } - 3 \\ 1 \\ 2 \end{array} \right)\).
  1. Prove by induction that \(\mathbf { a } _ { n } = \left( - \frac { 7 } { 8 } \right) ^ { n - 1 } \left( \begin{array} { l } 1 \\ 1 \\ 1 \end{array} \right)\). for all integers \(n \geqslant 1\).
  2. Use an algebraic method to find the smallest value of \(n\) such that \(\left| \mathbf { a } _ { n } \right| < 0.001\).

\section*{END OF QUESTION PAPER}

3 A sequence is defined by \(a _ { 1 } = 6\) and \(a _ { n + 1 } = 5 a _ { n } - 2\) for \(n \geqslant 1\).
Prove by induction that for all integers \(n \geqslant 1 , a _ { n } = \frac { 11 \times 5 ^ { n - 1 } + 1 } { 2 }\).