8.01b Induction: prove results for sequences and series

1.(a)By considering the series $$1 + t + t ^ { 2 } + t ^ { 3 } + \ldots + t ^ { n }$$ or otherwise,sum the series $$1 + 2 t + 3 t ^ { 2 } + 4 t ^ { 3 } + \ldots + n t ^ { n - 1 }$$ for \(t \neq 1\) .
(b)Hence find and simplify an expression for $$1 + 2 \times 3 + 3 \times 3 ^ { 2 } + 4 \times 3 ^ { 3 } + \ldots + 2001 \times 3 ^ { 2000 }$$ (c)Write down an expression for both the sums of the series in part(a)for the case where \(t = 1\) .

1 Verify that \(\frac { 1 } { n ^ { 2 } } - \frac { 1 } { ( n + 1 ) ^ { 2 } } = \frac { 2 n + 1 } { n ^ { 2 } ( n + 1 ) ^ { 2 } }\). Let \(S _ { N } = \sum _ { r = 1 } ^ { N } \frac { 2 r + 1 } { r ^ { 2 } ( r + 1 ) ^ { 2 } }\). Express \(S _ { N }\) in terms of \(N\). Let \(S = \lim _ { N \rightarrow \infty } S _ { N }\). Find the least value of \(N\) such that \(S - S _ { N } < 10 ^ { - 16 }\).

6 The Fibonacci sequence \(\left\{ F _ { n } \right\}\) is defined by \(F _ { 0 } = 0 , F _ { 1 } = 1\) and \(F _ { n } = F _ { n - 1 } + F _ { n - 2 }\) for all \(n \geqslant 2\).

1. Show that \(F _ { n + 5 } = 5 F _ { n + 1 } + 3 F _ { n }\)
2. Prove that \(F _ { n }\) is a multiple of 5 when \(n\) is a multiple of 5 .

7 Binet's formula for the \(n\)th Fibonacci number is given by \(\mathrm { F } _ { \mathrm { n } } = \frac { 1 } { \sqrt { 5 } } \left( \alpha ^ { \mathrm { n } } - \beta ^ { \mathrm { n } } \right)\) for \(n \geqslant 0\), where \(\alpha\) and \(\beta\) (with \(\alpha > 0 > \beta\) ) are the roots of \(x ^ { 2 } - x - 1 = 0\).

1. Write down the values of \(\alpha + \beta\) and \(\alpha \beta\).
2. Consider the sequence \(\left\{ \mathrm { S } _ { \mathrm { n } } \right\}\), where \(\mathrm { S } _ { \mathrm { n } } = \alpha ^ { \mathrm { n } } + \beta ^ { \mathrm { n } }\) for \(n \geqslant 0\).
   1. Determine the values of \(S _ { 2 }\) and \(S _ { 3 }\).
   2. Show that \(S _ { n + 2 } = S _ { n + 1 } + S _ { n }\) for \(n \geqslant 0\).
   3. Deduce that \(S _ { n }\) is an integer for all \(n \geqslant 0\).
3. A student models the terms of the sequence \(\left\{ \mathrm { S } _ { \mathrm { n } } \right\}\) using the formula \(\mathrm { T } _ { \mathrm { n } } = \alpha ^ { \mathrm { n } }\).
   1. Explain why this formula is unsuitable for every \(n \geqslant 1\).
   2. Considering the cases \(n\) even and \(n\) odd separately, state a modification of the formula \(\mathrm { T } _ { \mathrm { n } } = \alpha ^ { \mathrm { n } }\), other than \(\mathrm { T } _ { \mathrm { n } } = \alpha ^ { \mathrm { n } } + \beta ^ { \mathrm { n } }\), such that \(\mathrm { T } _ { \mathrm { n } } = \mathrm { S } _ { \mathrm { n } }\) for all \(n \geqslant 1\).

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?

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