Activity132
List all independent sets of \(P_1\text{,}\) \(P_2\text{,}\) and \(P_3\text{.}\) Don't forget the empty set! Do you notice a pattern among these numbers?
Hint
You should find 3 independent sets in \(P_1\) and 5 in \(C_4\text{.}\)
Section2.4Counting 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.
Given any graph \(G = (V, E)\text{,}\) an independent set (of vertices) is a subset \(I \subseteq V\) so that no two vertices in \(I\) are adjacent. Suppose you wished to count the number of independent sets of a particular graph. In this example, lets do so for the path \(P_{10}\) (i.e., the graph containing 11 vertices and 10 edges arranged in a line).
Let's label the vertices 1 through 11, and assume that vertices are adjacent to those with labels one more or one less than themselves (that is, the edge set is \(E = \{(i,i+1) \st 1 \le i \lt 11\}\)). How might you build an independent set?
A first attempt might be to start with vertex 1 and realize that you can put it in or keep it out of the independent set. So there are two choices for vertex 1. But now you might have two choices for vertex 2 (if vertex 1 was not in the set) or only once choice (to keep vertex 2 out, if vertex 1 was in the set). 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. 10 is way too big of a number; 1 would be much better. How many independent sets of \(P_1\) are there? Maybe then we also try the version with 2 and 3.
We get is a sequence \((a_n)_{n \ge 1}\) which gives the number of independent sets: the number of independent sets of \(P_n\) is simply \(a_n\text{.}\)
The sequence we get is \(3, 5, 8, 13, \ldots\text{.}\) It appears that this sequence satisfies a familiar recurrence relation, \(a_n = a_{n-1} + a_{n-2}\text{,}\) but unlike the Fibonacci sequence, here the initial terms are \(a_1 = 3\) and \(a_2 = 5\text{.}\) Is this appearance deceiving? Can we explain why this sequence should satisfy this recurrence?
Activity133
Explain why \(a_n\) satisfies the recurrence \(a_n = a_{n-1} + a_{n-2}\text{.}\) You will need to use the graphs \(P_n\text{,}\) \(P_{n-1}\) and \(P_{n-2}\) and their independent sets to do this. Show how you can “find” the independent sets of \(P_{n-1}\) and \(P_{n-2}\) among the independent set of \(P_{n}\) (perhaps using some sort of bijection).
Hint
Which independent sets contain the vertex \(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.
Subsection2.4.1Finding 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. Many of these context will be familiar, and you might be able to answer the counting questions with what we have already discovered. Don't do this. The point of these is to start thinking about these counting problems recursively.
Activity134
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.
Hint
You should ask yourself, how are the subsets of \([n]\) related to the subsets of \([n-1]\text{.}\) If you are stuck, you could always “cheat” and use your knowledge of the value of \(a_n\text{,}\) but try to do this without thinking about that.
Activity135
Let \(k_n\) be the number of edges in the complete graph \(K_n\text{.}\) Find a recurrence relation for the sequence \((k_n)_{n \ge 1}\) and prove you are correct.
Hint
What would you need to do to the graph \(K_n\) to get the graph \(K_{n-1}\text{?}\) How does this affect the number of edges?
Activity136
Let \(b_n\) be the number of bijections from an \(n\)-element set to and \(n\)-element set. Find a recurrence relation for the sequence \((b_n)_{n \ge 1}\) and prove you are correct.
Hint
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).
Activity137
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{.}\)
Hint
Suppose you already knew the number of moves needed to solve the puzzle with \(n-1\) rings.
Activity138
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?
Hint1
Hint2
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 activities above all have relatively simple recurrence relations. In particular, they all make reference only to one previous term. This need not be the case, as we saw when counting independent sets of paths and as the next few activities demonstrate.
Activity139
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\) (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.
Hint
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 an justify a recurrence relation for \((b_n)_{n \ge 1}\text{.}\)
Activity140
Let \(c_n\) be the number of independent sets of vertices in the cycle \(C_n\text{.}\) For consistency, label the vertices of \(C_n\) with the integers \(1, 2, \ldots, n\) and assume \(E = \{(i, i+1) \st 1 \le i \lt n\} \cup \{(n, 1)\}\text{.}\) Find a recurrence relation for \((c_n)_{n\ge 4}\) and prove you are correct.
Hint
Consider what happens to \(C_n\) when you contract along the edge \((n,1)\) (in other words, remove the edge and glue the vertices \(1\) and \(n\) together). This should give you a copy of \(C_{n-1}\text{.}\) Now think about which independent sets in \(C_n\) are not represented by independent sets in \(C_{n-1}\text{.}\)
Activity141
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 2.4.1.
Let \(t_n\) be the number of triangulations. Find a recurrence relation for \((t_n)_{n \ge 3}\text{.}\) Justify your answer.
Hint
Your recurrence relation will not have a fixed number of terms, but rather be in terms of all previous terms.
We will study the recurrence relation in Activity 141 again in Section 2.5. We mention it here because it is a nice example of how sometimes recurrence relations use up to all the previous terms of the sequence. Sometimes we can find a simpler recurrence relation that captures the same sequence.
Activity142
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.
Hint
Try this out with some different initial conditions. Once you see what the recurrence should be, proving it by induction should be easy.
Subsection2.4.2Using 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.
Activity143
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.
Hint
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{.}\)
Activity144
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.
Hint
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.
The sequence in Activity 143 is an example of an arithmetic sequence (or arithmetic progression) in that the difference between terms is constant. The sequence in Activity 144 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 143 is called telescoping and the method suggested for Activity 144 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.
Activity145
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{.}\)
(a)
In general, what is a recurrence relation for \((b_n)\text{?}\)
Hint
If you have calculated \(b_{n-1}\text{,}\) what do you need to do to get \(b_n\text{?}\)
(b)
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{.}\)
(c)
If \(a_n = \binom{n}{2}\text{,}\) find the sequence of partial sums \(b_n\text{.}\)
(d)
If \(a_n = F_n\text{,}\) the \(n\)-th Fibonacci number, find the sequence of partial sums \(b_n\text{.}\)
The sequences in the previous activity worked out nicely, but what can we say in general? Here are a few things.
Activity146
Let \((a_n)_{n \ge 1}\) be any arithmetic sequence. Say \(a_n = dn + c\) (so \(d\) is the common difference and \(c = a_0\)). 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?
Hint
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\text{.}\)
(c)
What is special about sums of arithmetic sequences that allow 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.
Activity147
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?
It is helpful to have a guess for the form of a closed formula. For example, if you believe that a sequence should have a closed formula that is say a cubic polynomial, then you can find a cubic polynomial that agrees with the first 4 terms of the sequence. This would be done by setting up a system of 4 equations with 4 unknowns and solving the system.
Another time this guess-and-check approach is reasonable is when we believe a sequence to be exponential.
Activity148
Consider the recurrence relation \(a_n = 5a_{n-1} - 6a_{n-2}\text{.}\)
(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.
Hint
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{.}\)
Hint
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{.}\)
Activity149
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 square/domino paths from Activity 139.)
Hint
Guess that \(r^n\) is a solution, and use this to find two roots \(r_1, r_2\) of a polynomial. Then use \(3 = \alpha r_1^1 + \beta r_1^1\) and \(13 = \alpha r_2^2 + \beta r_2^2\) to find \(\alpha\) and \(\beta\text{.}\)
Activity150
Find a closed formula for the \(n\)th Fibonacci number. This is called Binet's Formula.
Hint
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.
Subsection2.4.3Exploring the Fibonacci Sequence
¶We now have the tools to do a deep dive into the Fibonacci numbers, the most famous recursively defined sequence. The following activities are not strictly necessary for later material, but provide good practice in the techniques we have developed and are interesting in their own right.
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{.}\)
Activity151
Determine a formula for each of the following sums, and prove you are correct.
(a)
\(F_{0} + F_{1} + F_{2} + \ldots + F_{n}\text{.}\)
(b)
\(F_{0} + F_{2} + F_{4} + \ldots + F_{2n}\text{.}\)
Activity152
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{.}\)
Activity153
Determine a closed expression for \(F_{0}F_{3} + F_{1}F_{4} + \cdots + F_{n-1}F_{n+2}\) using Task 152.a.
Activity154
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 152.b and telescoping sums.
Activity155
Give a geometrical “proof” for the result in Activity 154.
Activity156
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.
Hint
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.
Activity157
Prove that \(F_{n - 1}F_{n + 1} - F_{n}^{2} = (-1)^{n}\) in two ways: First use mathematical induction. Then us Activity 156 and determinants.
Activity158
Is there a result analogous to that in Activity 157 for just the positive integers \(1, 2, 3, 4, \ldots\text{?}\)
Activity159
Show that \(Q^{2n + 1} = Q^{n}Q^{n+1}\) and that \(F_{2n + 1} = F_{n + 1}^{2} + F_{n}^{2}\) .
Activity160
Prove \(\left( \frac{n}{0} \right)F_{0} + \left( \frac{n}{1} \right)F_{1} + \ldots + \left( \frac{n}{n} \right)F_{n} = F_{2n}\) in two ways. First, use the Binet Formula from Activity 150. Then, use \(Q\text{.}\)
Activity161
Prove that \(\sum_{n = 2}^{\infty}\frac{1}{F_{n - 1}F_{n + 1}} = 1\text{.}\)
Hint
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{.}\)
Activity162
Prove that \(\sum_{n = 2}^{\infty}\frac{F_{n}}{F_{n - 1}F_{n + 1}} = 2.\)
Activity163
Prove that \(\lim_{n\to\infty}\frac{F_{n + 1}}{F_{n}} = \frac{1 + \sqrt{5}}{2}.\)
Activity164
For which values of \(n\) is \(F^{n}\) a multiple of 3?
Activity165
Can you have four distinct positive Fibonacci numbers in arithmetic progression?
Activity166
How many Fibonacci numbers are perfect squares?
Activity167
Find a closed formula for \(\frac{1}{F_{1}} + \frac{1}{F_{2}} + \frac{1}{F_{4}} + \frac{1}{F_{8}} + \ldots.\)
Activity168
Conjecture and prove a formula for \(\binom{n}{0} + \binom{n-1}{1} + \binom{n-2}{2} + \cdots\text{.}\)
Activity169
Prove that \(F_{5n + 5} = 3F_{5n} + 5F_{5n + 1}\text{.}\)
Hint
Use \(Q^{5n + 5}\text{.}\)
Activity170
Let \(\varphi\) be the positive root of \(x^{2} - x - 1 = 0\text{.}\) Prove that \(\varphi^{n} = F_{n}\varphi + F_{n - 1}\text{.}\)
Activity171
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).