2.5: Sequences

Last updated
Save as PDF

Page ID: 23447

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

We have already met

the sequence of natural numbers (1, 2, 3, 4, 5, ...),
the sequence of squares (1, 4, 9, 16, 25, ...),
the sequence of cubes (1, 8, 27, 64, 125, ...),
the sequence of prime numbers (2, 3, 5, 7, 11, 13, 17, ...),
the sequence of powers of 2 (1, 2, 4, 8, 16, 32, ...), and the sequence of powers of 4 (1, 4, 16, 64, 256, ...).

We have also considered

the sequence of units digits of the powers of 4 (1, 4, 6, 4, 6, 4, 6, ...),
the sequence of leading digits of the powers of 4 (1, 4, 1, 6, 2, 1, 4, ...).

2.5.1 Triangular numbers

Problem 54

(a) Evaluate the first twelve terms of the sequence of triangular numbers:

$\begin{matrix} 1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4, \dots, 1 + 2 + 3 + \dots + 10 + 11 + 12. \end{matrix}$

(b) Find and prove a formula for the n^th triangular number

$\begin{matrix} T_{n} = 1 + 2 + 3 + \dots + n . \end{matrix}$

2.5.2 Fibonacci numbers

The Hindu-Arabic numeral system emerged in the Middle East in the 10^thand 11^th centuries. Fibonacci, also known as Leonardo of Pisa, is generally credited with introducing this system to Europe around 1200 – especially through his book Liber Abaci (1202). One of the problems in that book introduced the sequence that now bears his name.

The sequence of Fibonacci numbers begins with the terms F₀ = 0, F₁ = 1, and continues via the Fibonacci recurrence relation:

$\begin{matrix} F_{n + 1} = F_{n} + F_{n - 1} . \end{matrix}$

The sequence was introduced through a curious problem about breeding rabbits; but to this day it continues to feature in many unexpected corners of mathematics and its applications.

Problem 55

(a) (i) Generate the first twelve terms of the Fibonacci sequence:

$\begin{matrix} F_{0}, F_{1}, \dots, F_{11} . \end{matrix}$

(ii) Use this to generate the first eleven terms of the sequence of “differences” between successive Fibonacci numbers. Then generate the first ten terms of the sequence of “differences between successive differences”.

(iii) Find an expression for the m^th term of the k^th sequence of differences.

(b) (i) Generate the first twelve terms of the sequence of powers of 2:

$\begin{matrix} 2^{0}, 2^{1}, 2^{2}, \dots, 2^{11} . \end{matrix}$

(ii) Use this to generate the first eleven terms of the sequence of “differences” between successive powers of 2. Then generate the first ten terms of the sequence of “differences between successive differences”.

(iii) Find an expression for the m^th term of the k^th sequence of differences.

The sequence of differences between successive terms in the sequence of triangular numbers is just the sequence of natural numbers (starting with 2):

$\begin{matrix} 2, 3, 4, 5, 6, \dots; \end{matrix}$ and the sequence of “second differences” is then constant: $\begin{matrix} 1, 1, 1, 1, 1, \dots . \end{matrix}$

The sequences of powers of 2 and the Fibonacci numbers behave very differently from this, in that taking differences reproduces something very like the initial sequence. In particular, taking differences can never lead to a constant sequence.

Logically the next four problems should wait until Chapter 6, where we address the delicate matter of “proof by mathematical induction”. However, that would deprive us of the chance to sample the kind of surprises that lie just beneath the surface of the Fibonacci sequence, and to experience the process of fumbling our way towards a structural understanding of the apparent patterns that emerge. Of course, each time we think we have managed to guess what seems to be true, we face the challenge of proof. Those who have not yet mastered “proof by induction” are encouraged to get what they can from the solutions, and to view this as an informal introduction to ideas that will be squarely addressed in Chapter 6.

Problem 56

(a) (i) Generate the sequence of partial sums of the sequence of powers of 2:

$\begin{matrix} 2^{0}, 2^{0} + 2^{1}, 2^{0} + 2^{1} + 2^{2}, 2^{0} + 2^{1} + 2^{2} + 2^{3}, \dots \end{matrix}$

(ii) Prove that each partial sum is 1 less than the next power of 2.

(b) (i) Generate the sequence of partial sums of the Fibonacci sequence:

$\begin{matrix} F_{0}, F_{0} + F_{1}, F_{0} + F_{1} + F_{2}, F_{0} + F_{1} + F_{2} + F_{3}, \dots \end{matrix}$

(ii) Prove that each partial sum is 1 less than the next but one Fibonacci number.

Problem 56(b) starts out with the observation that

$F_{0} + F_{1} = F_{3} - 1$

which is a consequence of the first two instances of the fundamental recurrence relation

$\begin{matrix} F_{n - 1} + F_{n} = F_{n + 1} \end{matrix}$ and derives a surprising value for the n^th partial sum: $\begin{matrix} F_{0} + F_{1} + F_{2} + \dots + F_{n - 1} . \end{matrix}$

Fibonacci numbers make their mathematical presence felt in a quiet way – partly through the almost spooky range of unexpected internal relations which they satisfy, as illustrated in Problem 56(b) and in the next few problems.

Problem 57

(a) Note that

$\begin{matrix} F_{n}^{2} = F_{n - 0} F_{n + 0} = F_{n}^{2} + {(- 1)}^{n - 1} F_{0} . \end{matrix}$

(i) Evaluate the succession of terms:

$\begin{matrix} F_{1 - 1} F_{1 + 1}, F_{2 - 1} F_{2 + 1}, F_{3 - 1} F_{3 + 1}, F_{4 - 1} F_{4 + 1}, \dots . \end{matrix}$

(ii) Guess a simpler expression for the product $F_{n - 1} F_{n + 1}$ . Prove your guess is correct.

(b) Let $a, b, c, d \geq 0$ .

(i) Show that the parallelogram OABC spanned by the origin O, and the points $A = (a, b), C = (c, d)$ and their sum $B = (a + c, b + d)$ has area $| a d - b c |$ .

(ii) Find the area of the first parallelogram in the sequence of “Fibonacci parallelograms”, spanned by the origin O, and the points $A = (F_{0}, F_{1}) = (0,1)$ , $C = (F_{1}, F_{2}) = (1,1)$ .

(iii) Show that the n^th parallelogram OACB in this sequence, spanned by the origin O, and the points $A = (F_{n - 1}, F_{n})$ and $B = (F_{n}, F_{n + 1})$ , and the ${(n + 1)}^{th}$ parallelogram OBDC spanned by the origin O, and the points $B = (F_{n}, F_{n + 1})$ and $C = (F_{n + 1}, F_{n + 2})$ overlap in the triangle OBC, which is exactly half of each parallelogram.

Conclude that every such parallelogram has area 1. Relate this to the conclusion of (a)(ii).

The basic recurrence relation for Fibonacci numbers specifies the next term as the sum of two successive terms. We now consider what this implies about the sum of the squares of two successive terms.

Problem 58

(a) Evaluate the first few terms of the sequence

$\begin{matrix} F_{0}^{2} + F_{1}^{2}, F_{1}^{2} + F_{2}^{2}, F_{2}^{2} + F_{3}^{2}, \dots . \end{matrix}$

(b) Guess a simpler expression for the sum $F_{n - 1}^{2} + F_{n}^{2}$ . Prove your guess is correct.

Problem 59

(a) Note that

$F_{0} F_{4} = 0 = F_{2}^{2} - 1, F_{1} F_{5} = 5 = F_{3}^{2} + 1.$

(i) Evaluate the succession of terms:

$\begin{matrix} F_{2 - 2} F_{2 + 2}, F_{3 - 2} F_{3 + 2}, F_{4 - 2} F_{4 + 2}, F_{5 - 2} F_{5 + 2}, F_{6 - 2} F_{6 + 2}, \dots . \end{matrix}$

(ii) Guess a simpler expression for the product $F_{n - 2} F_{n + 2}$ . Prove your guess is correct.

(b) (i) Evaluate the succession of terms:

$\begin{matrix} F_{3 - 3} F_{3 + 3}, F_{4 - 3} F_{4 + 3}, F_{5 - 3} F_{5 + 3}, F_{6 - 3} F_{6 + 3}, \dots . \end{matrix}$

(ii) Guess a simpler expression for the product $F_{n - 3} F_{n + 3}$ . Prove your guess is correct.