We will explore special sequences.

### 1 Sequences

A sequence is a list of numbers. The length of the sequence can be either finite or infinite. For example, the sequence of binomial coefficients, is a sequence of length when , whereas the sequence has infinitely many terms for . (Actually, if we recall from section 1.11, is defined to be for with , so the first sequence can be extended indefinitely with infinitely many zero terms.) We have also seen sequences defined recursively. Recall that for the derangement numbers we have for . As long as we have values for and (seeds), we can find and so on. We begin with some elementary sequences and then we will explore the important Fibonacci sequence.

According to the recursive formula for , we have \begin{align*} a_1 &= a_0 + d= a+d\\ a_2 &= a_1 + d= a+2d\\ a_3 &= a_2 + d= a+3d\\ a_4 &= a_3 + d= a+4d\\ \end{align*}

It is now clear that our conjecture is and we prove this by induction. The base case for is true as indicated above. We now suppose that for some and we want to show that . By the recursive definition of the sequence we have, and by the inductive hypothesis , so as desired. By induction, for all .

### 2 Fibonacci Sequence

Consider the following population problem: a pair of baby rabbits (one male, one female) reach adulthood after one month. Assuming that each month a pair of adult rabbits will produce a pair of baby rabbits (one male, one female), how many pairs of rabbits will there be after months? During month , we have one pair of baby rabbits which we will denote by r. During month , we have one pair of adult rabbits, R. During month , we have one pair of adult rabbits and one pair of baby rabbits, rR. During month , we have two pairs of adult rabbits and one pair of baby rabbits, rRR. And so on. If we know how many pairs of rabbits of each type we have during a particular month, then we can determine how may pairs of each type we will have during the next month and how many of each type we had during the previous month. For example, if we now have pairs of baby rabbits and pairs of adult rabbits, then the next month we will have pairs of adult rabbits and pairs of baby rabbits, for a total of pairs of rabbits. Furthermore, during the previous month we must have had pairs of adult rabbits and pairs of baby rabbits, for a total of pairs of rabbits. From this we can see that the number of rabbits at a particular time is the sum of the number of pairs of rabbits from the previous 2 months. This motivates the following definition of the Fibonacci sequence:

The first 10 terms of the Fibonacci sequence are We now look at some interesting properties of the sequence which can be proven using induction.

Base case: if then which is even.

Inductive Hypothesis: Suppose that is even for some .

Inductive Step: We want to show that is even.

By the recursive definition of the Fibonacci sequence, we have \begin{align*} f_{3n+3} &= f_{3n+1} + f_{3n+2}\\ &= f_{3n+1} + f_{3n} + f_{3n+1}\\ &= f_{3n} + 2f_{3n+1}\\ &= 2k + 2f_{3n+1} \;\;\text{since} \; f_{3n} \; \text{is even})\\ &= 2(k + f_{3n+1}) \end{align*}

which is even (i.e., a multiple of 2). Hence, is even for all .

Our next goal is to find a non-recursive formula for . To this end, we will examine the ratios of the terms of the Fibonacci sequence. Since we can divide by to obtain Taking the limit gives Assuming the limit on the left-hand side exists and equals the positive real number , we have Multiplying through by we see that satisfies the quadratic equation The quadratic formula gives and since , we have This number is called the golden ratio and its value is approximately . The other root of the quadratic is important in what follows, so we will denote it by : Note that and .

- Proof
- We will prove the proposition by strong induction. Due to the
nature of the recursive formula for the Fibonacci sequence, we will need
to assume that the formula holds in two successive cases, rather than just
one.

Base cases: if then the left-hand side is and the right-hand side is , so the result holds. If , then the left-hand side is and the right-hand side is Inductive hypotheses: Suppose that for some we have both Inductive step: we need to show that By the recursive definition of the Fibonacci sequence and the inductive hypothesis, we have \begin{align*} f_{n+2} &= f_{n} + f_{n+1}\\ & = \frac{\varphi ^n - \psi ^n}{\varphi - \psi } + \frac{\varphi ^{n+1} - \psi ^{n+1}}{\varphi - \psi }\\ &= \frac{(\varphi ^{n+1} + \varphi ^n) - (\psi ^{n+1}+ \psi ^n)}{\varphi - \psi }\\ &= \frac{\varphi ^n(\varphi + 1) - \psi ^n(\psi + 1 )}{\varphi - \psi }\\ &= \frac{\varphi ^n(\varphi ^2) - \psi ^n(\psi ^2 )}{\varphi - \psi }\\ &= \frac{\varphi ^{n+2} - \psi ^{n+2}}{\varphi - \psi } \end{align*}Note that the penultimate step follows from the fact that both and are solutions of the quadratic equation , which is equivalent to .

The Fibonacci numbers have an interesting relationship to the binomial coefficients.

- Proof
- We will use strong induction. For the base cases, and , we have so the
result holds in both cases.

Our inductive hypotheses are that the formula holds for some values and , i.e., We now wish to show that We will need Pascal’s Identity which we recall states that We have \begin{align*} f_{n+2} &= f_n + f_{n+1}\;\; \text{(recursive definition of Fibonacci sequence)}\\ &= \sum _{k=0}^{n-1} \binom{n-1-k}{k} + \sum _{k=0}^{n} \binom{n-k}{k} \;\;\text{(inductive hypotheses)}\\ &= \sum _{k=1}^{n} \binom{n-k}{k-1} + \sum _{k=0}^{n} \binom{n-k}{k} \;\;\text{(re-indexing)}\\ &= \sum _{k=1}^{n} \binom{n-k}{k-1} + \binom{n}{0} + \sum _{k=1}^{n} \binom{n-k}{k} \;\;\text{(separating the first term)}\\ &= \binom{n}{0} + \sum _{k=1}^{n} \left [\binom{n-k}{k-1} + \binom{n-k}{k} \right ] \;\;\text{(combining sums)}\\ &= \binom{n}{0} + \sum _{k=1}^{n} \binom{n+1-k}{k} \;\;\text{(Pascal's Identity)}\\ &= \binom{n+1}{0} + \sum _{k=1}^{n} \binom{n+1-k}{k} \;\;\text{(since} \;\binom{n}{0} = \binom{n+1}{0} = 1)\\ &= \sum _{k=0}^{n} \binom{n+1-k}{k}\;\;\text{(since} \binom{n+1}{0} \;\; \text{corresponds to} \;\; k = 0) \\ &= \sum _{k=0}^{n+1} \binom{n+1-k}{k} \;\;\text{(since} \;\; \binom{0}{n+1} = 0)\\ \end{align*}which is what we needed to show.

Below is a visualization of the proposition (thanks to github user eankeen):

### 3 Fibonacci, Dominoes and Chess Boards

We now investigate a counting problem that involves covering a chess board with dominoes. A normal chess board is with squares. Our chess boards will be with squares. A domino will cover two squares on our board and the question is: how many ways are there to cover our board with dominoes? If , the answer is obviously . If we see from the figure below that the answer is .

For , there are 3 possibilities as shown below:

- Proof
- We use strong induction. Suppose that the number of ways to cover
a board is and that the number of ways to cover a board is . We have seen
that this is true for , establishing our base cases. We now need to show that the
number of coverings of a board is . We partition the coverings into two groups.

Group 1) The domino that covers the upper left hand square is vertical. The number of coverings of the board belonging to this group is simply the number of coverings of the board that lies to the right of this vertical tile. By our inductive hypotheses, this is .

Group 2) The domino that covers the upper left hand square is horizontal. This means that the domino below is also horizontal. The remaining part of the board that is not yet covered is and by the inductive hypotheses, the number of ways to complete the covering is .

Since every covering belongs to either group 1 or group 2 and these two groups do not have any coverings in common (i.e. they form a partition of the set of all coverings), the number of coverings of a board is which equals by the recursive definition of the Fibonacci sequence.

for

for

for

for