(problem 1a) Let and define the sequence recursively by and . (This is known as a
geometric sequence.) Find then conjecture a formula for . Verify your conjecture
using mathematical induction.
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.
Example 1 Let and define the sequence recursively by and . (This is known as an
arithmetic sequence.) Find then conjecture a formula for . Verify your conjecture
using mathematical induction.
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*}
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 .
(problem 1b) Consider the sequence of partial sums of the geometric sequence from
problem 1a. That is, let Use induction (with base case ) to prove that for
(problem 1c) Define the sequence recursively by and . Find then conjecture a
formula for . Verify your conjecture using mathematical induction.
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.
example 2 Use induction to prove that for each is even.
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*}
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.
(problem 3a) Show that the number of ways to cover a chess board with dominoes
and monominoes is also .
(problem 3b) Find a recursion relation that describes the number of ways to color the
squares of a chess board if each square is colored either red or blue and consecutive
squares may not be colored red.
for
for
for
for
for
(problem 3c) Find a recursion relation that describes the number of ways to color the
squares of a chess board if each square is colored either red, white or blue and
consecutive squares may not be colored red.
2024-09-27 14:05:23 for
for
for
for
for