Section 1.4 Counting with Recursion
¶What happens when you get stuck on a counting problem? It is quite easy to miss the clever way of thinking about breaking down a task that leads to a solution. Here is an example.
Your favorite milk-shake diner has 11 stools along the bar. Patrons of the diner have a rule that no two adjacent stools can be simultaneously occupied. In how many ways can the stools be occupied by any number of patrons (including no patrons at all, leaving all stools unoccupied)?
A first attempt might be to start with stool 1 and realize that it can be sat on or not. So there are two choices for stool 1. But now you might have two choices for stool 2 (if stool 1 was not sat on) or only once choice (to keep stool 2 empty, if stool 1 was in use). Okay, so the multiplicative principle doesn't help.
Say you can't think of anything else to try. The problem seems just too hard. So make it easier: 11 is way too big of a number; 1 would be much better. How many ways could a row of 1 stool be occupied? Let's call this number \(S_1\text{.}\) Maybe then we also try the version with 2 and 3 stools.
Activity 67.
List all stool seating charts with 1, 2, and 3 stools. Let the number of seating charts be called \(S_1\text{,}\) \(S_2\text{,}\) and \(S_3\) respectively. Do you notice a pattern among these numbers?
You should find 3 seating arrangements with 2 stools. There are 5 with three stools.
We get a sequence \((S_n)_{n \ge 1}\) which gives the number of seating charts.
The sequence we get is \(2, 3, 5, 8, 13, \ldots\text{.}\) It appears that this sequence satisfies a familiar recurrence relation of the Fibonacci sequence: \(S_n = S_{n-1} + S_{n-2}\text{.}\) But unlike the Fibonacci sequence, here the initial terms are \(S_1 = 2\) and \(S_2 = 3\text{.}\) Is this appearance deceiving? Can we explain why this sequence should satisfy this recurrence?
Activity 68.
Explain why \(S_n\) satisfies the recurrence \(S_n = S_{n-1} + S_{n-2}\text{.}\) You will need to consider seating charts with \(n\text{,}\) \(n-1\) and \(n-2\) stools. Show how you can “find” the seating charts for \(n-1\) and \(n-2\) stools among those for \(n\) stools (perhaps using some sort of bijection).
Which seating charts have someone on stool \(n+1\text{?}\)
Once we have a proof that our sequence really does give the answers to all the versions of the counting question we are interested in, then we can start investigating properties of this sequence. Sometimes, we might even be able to find a closed formula for the \(n\)th term of the sequence, so we can compute values without relying on the recurrence.
Subsection 1.4.1 Finding Recurrence Relations
¶Before investigating properties of sequences given by recurrence relations, we must be able to find those sequences and the recurrence relations. The following activities give some practice with moving from a counting question to a recurrence relation for the sequence of answers. You might be able to answer the counting questions with what we have already discovered, but do not do this. The point of these is to start thinking about these counting problems recursively.
First, here is an example of what we are looking for.
Example 1.4.1.
Let \(a_n\) be the number of subsets of \([n]\text{.}\) Find a recurrence relation for the sequence \((a_n)_{n \ge 0}\text{.}\) Prove the recurrence relation is correct.
Start by enumerating the sequence \((a_n)_{n \ge 0}\text{.}\) There is only 1 subset of the empty set (so \(a_0 = 1\)). There are two subsets of \([1]\text{,}\) and four subsets of \([2]\text{.}\) So the sequence looks like \(1, 2, 4, 8, \ldots\text{.}\) It appears that the recurrence relation should be \(a_n = 2a_{n-1}\) with initial condition \(a_0 = 1\text{.}\)
To prove this is correct, we must reference the things we are counting (saying that the recurrence agrees with the finitely many terms we have listed is NOT enough). Consider the \(a_{n-1}\) different subsets of \([n-1]\text{.}\) Each of these is a subset of \([n]\text{,}\) in particular, a subset of \([n]\) that does not include the number \(n\) as an element. Further, to each of these sets, we can add the element \(n\) to get another distinct subset of \([n]\text{.}\) So far, we have found \(2a_{n-1}\) subsets of \([n]\text{.}\) Actually, we have found all of them: every subset of \([n]\) either includes \(n\) or it does not.
Now here are some for you to try.
Exercise 69.
Let \(k_n\) be the number of handshakes that take place if all \(n\) people in a room shake hands with everyone there exactly once. Find a recurrence relation for the sequence \((k_n)_{n \ge 1}\) and prove you are correct.
How many new handshakes occur when a new person enters the room?
Exercise 70.
Let \(b_n\) be the number of bijections from an \(n\)-element set to an \(n\)-element set. Find a recurrence relation for the sequence \((b_n)_{n \ge 1}\) and prove you are correct.
To determine a bijection \(f:[n] \to [n]\text{,}\) you could first say what \(f(n)\) is. What do you still need to do? Your answer to this question should be one single step (that inductively, you know how to do).
Exercise 71.
The “Towers of Hanoi” puzzle has three rods rising from a rectangular base with \(n\) rings of different sizes stacked in decreasing order of size on one rod. A legal move consists of moving a ring from one rod to another so that it does not land on top of a smaller ring. If \(m_n\) is the number of moves required to move all the rings from the initial rod to another rod that you choose, give a recurrence for \(m_n\text{.}\)
Suppose you already knew the number of moves needed to solve the puzzle with \(n-1\) rings.
Exercise 72.
We draw \(n\) mutually intersecting circles in the plane so that each one crosses each other one exactly twice and no three intersect in the same point. (As examples, think of Venn diagrams with two or three mutually intersecting sets.) Find a recurrence for the number \(r_n\) of regions into which the plane is divided by \(n\) circles. (One circle divides the plane into two regions, the inside and the outside.) Find the number of regions with \(n\) circles. For what values of \(n\) can you draw a Venn diagram showing all the possible intersections of \(n\) sets using circles to represent each of the sets?
If we have \(n - 1\) circles drawn in such a way that they define \(r_{n-1}\) regions, and we draw a new circle, each time it crosses another circle, except for the last time, it finishes dividing one region into two parts and starts dividing a new region into two parts.
Compare \(r_n\) with the number of subsets of an \(n\)-element set.
The sequences above all have relatively simple recurrence relations. In particular, the recursions all make reference only to one previous term. This need not be the case, as we saw when counting bar stool seating charts and as the next few problems demonstrate.
Exercise 73.
Suppose you have a large number of \(1\times 1\) squares and \(1 \times 2\) dominoes. You wish to use these to tile a \(1 \times n\) path. For \(n = 4\text{,}\) some examples of different paths are \(ssss\text{,}\) \(ssd\text{,}\) \(sds\text{,}\) \(dss\text{,}\) \(dd\text{,}\) using \(s\) for square and \(d\) for domino (in fact, these are all 5 of the possible paths).
(a)
Let \(a_n\) be the number of ways to tile the \(1 \times n\) path. Find a recurrence relation for the sequence \((a_n)_{n \ge 1}\text{,}\) and prove you are correct.
List out the first few values of \(a_n\) by enumerating all paths.
(b)
Now suppose your squares come in 3 colors and the dominoes come in 4 colors. Let \(b_n\) count the number of paths you can tile. Find and justify a recurrence relation for \((b_n)_{n \ge 1}\text{.}\)
Exercise 74.
Consider a convex \(n\)-gon with labeled vertices. In how many ways can diagonals be inserted so as to decompose the \(n\)-gon into triangles? For \(n = 5\) the five figures are shown in Figure 1.4.2.
Let \(t_n\) be the number of triangulations. Find a recurrence relation for \((t_n)_{n \ge 3}\text{.}\) Justify your answer.
Your recurrence relation will not have a fixed number of terms, but rather be in terms of all previous terms.
Fix an edge of the polygon. There will be exactly \(n-2\) triangles this edge could be part of. For each of those, can you count the number of triangles that can be made of what is left?
We will study the recurrence relation in Exercise 74 again in Section 1.5. We mention it here because it is a nice example of how sometimes recurrence relations use all the previous terms of the sequence. Sometimes we can find a simpler recurrence relation that captures the same sequence.
Exercise 75.
Consider the sequence \((a_n)_{n \ge 1}\) which satisfies the recurrence relation \(a_n = \sum_{i = 1}^{n-1} a_i\text{.}\) That is, each term of the sequence is the sum of all previous terms in the sequence.
Find a recurrence relation in terms of only the previous term for this sequence. Prove that you are correct.
Try this out with some different initial conditions. Once you see what the recurrence should be, proving it by induction should be easy.
Subsection 1.4.2 Using Recurrence Relations
¶While it is often easier to find a recurrence relation governing a sequence, if we wish to use sequences to solve counting problems, we would really like to be able to find a closed formula for the terms in a sequence. If this is not possible, we can still use the recurrence relation to learn something about how the sequence behaves.
We will start by consider some simple classes of recurrence relations for which we can find closed formulas.
Activity 76.
Let \((a_n)_{n \le 0}\) satisfy \(a_n = a_{n-1} + 3\) with \(a_0 = 2\text{.}\) For example, \(a_n\) might give the number of push-ups you can do \(n\) days into your training, assuming you can do 3 more push-ups each day, if you could do 2 push-ups before you started training. Find a closed formula for \(a_n\) and justify your answer. Show how the recurrence relation is used.
If you write out the sequence, it would be easy to guess at a closed formula, but the point here is to use the recurrence relation somehow. Consider rewriting the recurrence relation as \(a_n - a_{n-1} = 2\text{.}\) Note that \(a_n - a_0 = (a_n - a_{n-1}) + (a_{n-1} + a_{n-2}) + \cdots + (a_2 - a_1) + (a_1 - a_0)\text{.}\)
Activity 77.
Let \((a_n)_{n \le 0}\) satisfy \(a_n = 3a_{n-1}\) with \(a_0 = 2\text{.}\) For example, \(a_n\) might give the number of \(n\)-scoop ice-cream cones you can make from 3 available flavors in one of two kinds of cones. Find a closed formula for \(a_n\) and justify your answer. Show how the recurrence relation is used.
Again, if you write out the sequence, it would be easy to guess at a closed formula. To see how the recurrence relation is used, try substituting in earlier values. For example, \(a_2 = 3a_1\text{,}\) but \(a_1 = 3a_0\text{,}\) so \(a_2 = 3(3a_0) = 3^2a_0\text{.}\)
The sequence in Activity 76 is an example of an arithmetic sequence (or arithmetic progression) in that the difference between terms is constant. The sequence in Activity 77 is an example of a geometric sequence (or geometric progression) because the ratio between terms is constant. Of course there is nothing special about 2 and 3 in the activities, so you should now see how to find the closed formula for any arithmetic or geometric sequence.
The techniques used to get those closed formulas are also worth pointing out. The method suggested in the hint to Activity 76 is called telescoping and the method suggested for Activity 77 is called iteration.
Most sequences are not arithmetic, but it is still helpful to look at the difference between terms. Often if we know something about the sequence of differences, we can deduce something about the original sequence. We can also think about this as starting with the sequence of differences.
Given any sequence \((a_n)_{n \ge 1}\text{,}\) we can form the sequence of partial sums \((b_n)_{n \ge 1}\) given by \(b_n = \sum_{i = 1}^n a_n\text{.}\) That is, \(b_n\) tells you what you get if you add up the first \(n\) terms of \((a_n)\text{.}\)
Note that \((b_n)\) satisfies the recurrence relation \(b_n = b_{n-1} + a_n\text{,}\) or equivalently \(b_n - b_{n-1} = a_n\text{.}\) So \((a_n)\) is the sequence of differences of its sequence of partial sums!
Example 1.4.3.
If \((a_n)_{n \ge 1}\) is the familiar sequence \(1, 2, 3, 4, \ldots,\text{,}\) what is the sequence of partial sums?
The sequence of partial sums is \(1, 3, 6, 10, 15, \ldots\text{;}\) the triangular numbers (so called because you can arrange those numbers of dots into equilateral triangles). A closed formula for these is \(T_n = \frac{n(n+1)}{2}\text{,}\) which can be found as follows:
| \(T_n =\) | \(1\) | \(+\) | \(2\) | \(+ \cdots +\) | \((n-1)\) | \(+\) | n |
| \(+ \quad T_n =\) | \(n\) | \(+\) | \((n-1)\) | \(+ \cdots +\) | \(2\) | \(+\) | 1 |
| \(2T_n =\) | \((n+1)\) | \(+\) | \((n+1)\) | \(+ \cdots +\) | \((n+1)\) | \(+\) | \((n+1)\) |
The right hand side contains \(n\) summands, all identical, so \(2T_n = n(n+1)\text{.}\) Divide by 2!
Notice also that these triangular numbers appear as the third diagonal of Pascal's triangle. That is, \(T_n = \binom{n+1}{2}\text{.}\) Using the factorial formula for \(\binom{n+1}{2}\) confirms this.
Exercise 78.
(a)
If \((a_n)_{n \ge 1}\) is the sequence \(1, 3, 5, 7, 9, \ldots\text{,}\) find the sequence of partial sums \((b_n)\text{.}\)
(b)
If \(a_n = \binom{n}{2}\text{,}\) find the sequence of partial sums \((b_n)\text{.}\)
(c)
Consider the Fibonacci sequence \((F_n)_{n \ge 1}\text{,}\) starting \(1, 1, 2, 3, 5, \ldots\text{,}\) and satisfying the recurrence relation \(F_n = F_{n-1} + F_{n-2}\text{.}\) Find the sequence of partial sums. How do the terms relate to the original sequence?
The sequences in the previous problem worked out nicely, but what can we say in general? Here are a few things.
Activity 79.
Let \((a_n)_{n \ge 1}\) be any arithmetic sequence. Say \(a_n = dn + c\) (so \(d\) is the common difference and \(c = a_1 - d = a_0\text{,}\) if \(a_0\) were part of the sequence). What can we say about the closed formula for \(b_n = \sum_{i=1}^n a_i\text{?}\)
(a)
As an example, what is \(2+5+8+11+\cdots + 470\text{?}\) You might call this sum \(S\) and calculate:
| \(S =\) | \(2\) | \(+\) | \(5\) | \(+\) | \(8\) | \(+ \cdots +\) | \(467\) | \(+\) | 470 |
| \(+ \quad S =\) | \(470\) | \(+\) | \(467\) | \(+\) | \(464\) | \(+ \cdots +\) | \(5\) | \(+\) | 2 |
| \(2S =\) | \(472\) | \(+\) | \(472\) | \(+\) | \(472\) | \(+ \cdots +\) | \(472\) | \(+\) | \(472\) |
Why is that helpful? What is the sum?
You will need to decide how many terms are on the right-hand side.
(b)
Generalize the previous computation to find the closed formula for \(b_n = \sum_{i=1}^n a_i\text{.}\)
(c)
What is special about sums of arithmetic sequences that allows you to do this computation? Explain.
The previous activity shows that the sequence of partial sums of an arithmetic sequence is always a quadratic sequence. Conversely, any quadratic sequence should arise in this way.
Activity 80.
Given a sequence \((b_n)_{n \ge 1}\) with a quadratic closed formula, say \(b_n = an^2 + bn + c\text{,}\) what will the closed formula for the sequence of differences be? That is, what is the closed formula for \(a_n = b_n - b_{n-1}\text{?}\) Why does this show that every quadratic sequence is the sequence of partial sums for some arithmetic sequence?
The above observations can be generalized: a cubic sequence will have quadratic difference, a quartic sequence will have cubic differences, and so on. This allows us to guess at the form of a closed formula for a polynomial sequence by taking successive differences. If the “third differences” of a sequence are constant, then we would guess we could find a cubic polynomial. Given the first 4 terms, we can fit the cubic to them by setting up a system of 4 equations and 4 unknowns.
Sequences of partial sums are also useful for geometric sequences. The following technique will likely be familiar from calculus when you worked with geometric series.
Activity 81.
What is \(3 + 6 + 12 + 24 + \cdots + 12288\text{?}\) Call the sum \(S\) and compute \(S - 2S\text{.}\)
To better see what happened in the above example, try writing it this way:
| \(S=\) | \(3 \, +\) | \(6 + 12 + 24 + \cdots + 12288\) | |
| \(- \qquad 2S=\) | \(6 + 12 + 24 + \cdots + 12288\) | \(+ 24576\) | |
| \(-S = \) | \(3 \, +\) | \(0 + 0 + 0 + \cdots + 0 \) | \(-24576\) |
Then divide both sides by \(-1\) and we have the same result for \(S\text{.}\) The idea is, by multiplying the sum by the common ratio, each term becomes the next term. We shift over the sum to get the subtraction to mostly cancel out, leaving just the first term and new last term.
Exercise 82.
Find a closed formula for \(S_n = 2 + 10 + 50 + \cdots + 2\cdot 5^n\text{.}\)
Compute \(S_n - 5S_n\)
Notice that this is precisely the standard method used for converting repeating decimals to fractions.
Exercise 83.
Express \(N = 0.464646\ldots\) as a fraction by computing \(N - 0.01N\text{.}\) Why is this the same as computing an infinite geometric sum?
Here is a surprising use of these geometric sums to answer a counting question:
Exercise 84.
How many license plates consist of 6 symbols, using only the three numerals 1, 2, and 3 and the four letters a, b, c, and d, so that no numeral appears after any letter? For example, “31ddac” and “123211” are acceptable license plates, but “13ba2c” is not.
(a)
First answer this question by considering different cases: how many of the license plates contain no numerals? How many contain one numeral, etc. Find the sum.
The number of plates that have 2 numerals and (therefore) 4 letters is \(3^2\cdot 4^4\text{,}\) as there are 3 choices for each of the numerals, and 4 choices for each of the letters.
(b)
Recognize that that the total \(S\) when written this way is the sum of a (finite) geometric sequence. Compute \(S - \frac{3}{4}S\) to conclude that the answer can be expressed as \(4^7 - 3^7\text{.}\)
(c)
Generalize! What if a license plate has \(n\) symbols?
Guessing the form of a closed formula is also reasonable when we believe a sequence to be exponential.
Activity 85.
Consider the recurrence relation \(a_n = 5a_{n-1} - 6a_{n-2}\text{.}\) Listing terms (with some reasonable initial conditions) suggests that this sequence grows exponentially.
(a)
Show that \(a_n = 2^n\) and \(a_n = 3^n\) are both solutions to the recurrence relation. That is, they are sequences for which the recurrence relation holds.
You could do a full proof by induction here, but really you are just plugging these in to see if the recurrence works for them.
(b)
Show that if \(\alpha\) and \(\beta\) are any constants, \(a_n = \alpha 2^n + \beta 3^n\) is also a solution to the recurrence relation.
(c)
Might there be another solution to the recurrence relation? Suppose \(a_n = r^n\) for some non-zero constant \(r\text{.}\) Show that \(r = 2\) or \(r = 3\text{.}\)
If you do the substitution, you will get a degree \(n\) polynomial equation in the variable \(r\text{.}\) Solving that equation amounts to finding the roots of the polynomial.
This is a partial justification of the characteristic root technique (the polynomial whose roots are the base of the exponentials is called the characteristic polynomial). Making the reasonable guess that recurrence relations which give \(a_n\) as a linear combination of \(a_{n-1}\) and \(a_{n-2}\) should have exponential closed formulas allows you to find the bases of those exponentials. You can then use the initial conditions to find the constants \(\alpha\) and \(\beta\text{.}\) Let's illustrate this process with an example.
Example 1.4.4.
Find a closed formula for the sequence \((a_n)_{n \ge 1}\) given recursively by \(a_n = 3a_{n-1} + 4a_{n-2}\) with initial conditions \(a_1 = 3\) and \(a_2 = 13\text{.}\) (This is the sequence of colorful square/domino paths from Exercise 73.)
From the recurrence relation we have \(a_n - 3a_{n-1} - 4a_{n-2} = 0\text{.}\) We transform this into the characteristic equation \(x^2 - 3x - 4 = 0\text{.}\) This has roots \(x = 4\) and \(x = -1\text{.}\) So we guess that the closed formula for \(a_n\) will be \(a_n = \alpha 4^n + \beta (-1)^n\text{.}\)
To find \(\alpha\) and \(\beta\text{,}\) we use the initial conditions. When \(n = 1\) we have \(3 = 4\alpha -\beta\text{.}\) When \(n = 2\) we have \(13 = 16\alpha + \beta\text{.}\) It is easy to solve this system of two equations and two unknowns (simply adding them together eliminates the \(\beta\)). We find \(\alpha = \frac{4}{5}\) and \(\beta = \frac{1}{5}\text{.}\)
Thus the closed formula is
Exercise 86.
How many \(1\times n\) paths can you make from \(1\times 1\) squares that come in 2 colors and \(1\times 2\) dominoes that come in 3 colors?
(a)
First write down a recurrence relation and initial conditions for this problem.
(b)
Solve the recurrence relation using the characteristic root technique.
Exercise 87.
Find a closed formula for the \(n\)th Fibonacci number \(F_n\text{,}\) where \(F_1 = 1 = F_2\) and \(F_n = F_{n-1} + F_{n-2}\text{.}\) From the form of this recurrence, the characteristic root technique should work here. (The formula you will find is called Binet's Formula.)
You will need to use the quadratic formula to find the roots, and some careful algebra to find the coefficients. The closed formula will include \(\frac{1+\sqrt{5}}{2}\text{,}\) the Golden Ratio.
There are many subtle and interesting variations on solving recurrence relations, and we will not explore them all here. To conclude though, we consider one interesting case that will show up later as well.
Activity 88.
Consider the recurrence relation \(a_n = 2a_{n-1} - a_{n-2}\) with initial conditions \(a_0 = 1\) and \(a_1 = 2\text{.}\)
(a)
What goes wrong when you (blindly) apply the characteristic root technique?
(b)
Write out the first few terms of the sequence to guess at the closed formula. Verify it is correct.
As you saw above, something goes wrong with the characteristic root technique when the roots of the characteristic equation are repeated. One way around this is to guess that the closed formula should be
where \(r\) is the repeated root and \(\alpha\) and \(\beta\) are constants determined by the initial conditions as normal. The key here is to add an extra multiple of \(n\) to the second term.
Exercise 89.
Consider the recurrence relation \(a_n = 4a_{n-1} - 4a_{n-2}\text{.}\)
(a)
Find the general solution (leaving \(\alpha\) and \(\beta\) as parameters).
(b)
Find the solution with initial conditions \(a_0 = 1\) and \(a_1 = 2\text{.}\)
(c)
Find the solution with initial conditions \(a_0 = 1\) and \(a_1 = 8\text{.}\)
Subsection 1.4.3 Exploring the Fibonacci Sequence
¶Even though we are thinking of sequences as a tool for solving counting questions, it is often very rewarding to step back and observe the beauty and elegance of a sequence in its own right. So to conclude this section, we will consider a few delightful observations about the most famous recursively defined sequence: the Fibonacci numbers.
For consistency, let's agree that \(F_n\) is the \(n\)th Fibonacci number, where \(F_0 = 0\) and \(F_1 = 1\text{,}\) and for all other \(n\text{,}\) \(F_n = F_{n-1} + F_{n-2}\text{.}\)
Example 1.4.5.
Determine a formula for the sum \(F_{0} + F_{1} + F_{2} + \ldots + F_{n}\text{.}\)
If we collect some initial data we see that the sequence of partial sums is \(0, 1, 2, 4, 7, 12, 20, \ldots\text{.}\) We might recognize these numbers as always one less than a Fibonacci number, and guess that
We could prove this by induction, but for fun, here is a clever observation that finishes the problem: \(F_k = F_{k+2} - F_{k+1}\) (just rearrange the recurrence relation). Now replace each term after \(F_0\text{:}\)
Almost every term cancels (telescopes) leaving only
which is of course what we are looking for.
Exercise 90.
Determine a formula for the sum \(F_{0} + F_{2} + F_{4} + \ldots + F_{2n}\text{.}\)
Exercise 91.
Prove each of the following identities.
(a)
\(F_{n + 1}^{2} - F_{n}^{2} = F_{n - 1}F_{n + 2}\text{.}\)
(b)
\(F_{k}^{2} = F_{k}(F_{k + 1} - F_{k - 1})\text{.}\)
Exercise 92.
Determine a closed expression for \(F_{0}F_{3} + F_{1}F_{4} + \cdots + F_{n-1}F_{n+2}\) using Task 91.a.
Exercise 93.
Determine a formula for \(F_{1}^{2} + F_{2}^{2} + \ldots + F_{n}^{2}\) in two ways. First collect data and then prove your conjecture by mathematical induction. Second, use Task 91.b and telescoping sums.
Exercise 94.
Give a geometrical “proof” for the result in Exercise 93.
Exercise 95.
Consider the \(2\times 2\) matrix \(Q = \begin{pmatrix} 0 \amp 1\\ 1 \amp 1 \end{pmatrix}.\) Using standard matrix multiplication, compute \(Q^2 = Q\cdot Q\text{,}\) \(Q^3\text{,}\) and so on. Conjecture a formula for \(Q^n\) and prove you are correct.
You should find that \(Q^n = \begin{pmatrix} F_{n - 1} \amp F_{n}\\ F_{n} \amp F_{n + 1} \end{pmatrix}\text{.}\) Now prove this by induction.
Exercise 96.
Prove that \(F_{n - 1}F_{n + 1} - F_{n}^{2} = (-1)^{n}\) in two ways: First use mathematical induction. Then use Exercise 95 and determinants. There is also a nice “picture proof.”
Exercise 97.
Is there a result analogous to that in Exercise 96 for just the positive integers \(1, 2, 3, 4, \ldots\text{?}\)
Exercise 98.
Show that \(Q^{2n + 1} = Q^{n}Q^{n+1}\) and that \(F_{2n + 1} = F_{n + 1}^{2} + F_{n}^{2}\) .
You were asked above to prove the following Binet formula:
where \(a\) and \(b\) are the roots of \(x^2 - x - 1\text{.}\) The next example shows an interesting use of this formula.
Example 1.4.6.
Prove \(\binom{n}{0}F_{0} + \binom{n}{1}F_{1} + \ldots + \binom{n}{n}F_{n} = F_{2n}\) in two ways. First, use the Binet Formula from Exercise 87.
Starting on the right side, use the Binet formula and the fact that \(a\) and \(b\) satisfy \(x^2 - x - 1 = 0\text{:}\)
Then expand the two binomials using the binomial theorem:
Now group like terms:
You might also try proving this using the matrix \(Q\text{.}\)
Exercise 99.
Prove that \(\sum_{n = 2}^{\infty}\frac{1}{F_{n - 1}F_{n + 1}} = 1\text{.}\)
Show first that \(\frac{1}{F_{n - 1}F_{n + 1}} = \frac{1}{F_{n - 1}F_{n}} - \frac{1}{F_{n}F_{n + 1}}\text{.}\)
Exercise 100.
Prove that \(\sum_{n = 2}^{\infty}\frac{F_{n}}{F_{n - 1}F_{n + 1}} = 2.\)
Exercise 101.
Prove, directly from the recursion for \(F_n\text{,}\) that \(\lim_{n\to\infty}\frac{F_{n + 1}}{F_{n}} = \frac{1 + \sqrt{5}}{2}.\)
Exercise 102.
For which values of \(n\) is \(F^{n}\) a multiple of 3?
Exercise 103.
Can you have four distinct positive Fibonacci numbers in arithmetic progression?
Exercise 104.
Find a closed formula for \(\frac{1}{F_{1}} + \frac{1}{F_{2}} + \frac{1}{F_{4}} + \frac{1}{F_{8}} + \ldots.\)
Exercise 105.
Conjecture and prove a formula for \(\binom{n}{0} + \binom{n-1}{1} + \binom{n-2}{2} + \cdots\text{.}\)
Exercise 106.
Prove that \(F_{5n + 5} = 3F_{5n} + 5F_{5n + 1}\text{.}\)
Use \(Q^{5n + 5}\text{.}\)
Exercise 107.
Let \(\varphi\) be the positive root of \(x^{2} - x - 1 = 0\text{.}\) Prove that \(\varphi^{n} = F_{n}\varphi + F_{n - 1}\text{.}\)
Exercise 108.
Can every positive integer be written as a sum of distinct Fibonacci numbers? In fact, can every positive integer be written as a sum of non-consecutive Fibonacci numbers? Further, can every positive integer be written as a sum of at most 5 non-consecutive Fibonacci numbers? Prove your answers (i.e., either give a proof or provide a counterexample).