Loading [MathJax]/extensions/TeX/mathchoice.js
Skip to main content

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), an independent set (of vertices) is a subset IβŠ†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 P10 (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):1≀i<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 P1 are there? Maybe then we also try the version with 2 and 3.

Activity132

List all independent sets of P1, P2, and P3. 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{.}\)

We get is a sequence (an)nβ‰₯1 which gives the number of independent sets: the number of independent sets of Pn is simply an.

The sequence we get is 3,5,8,13,…. It appears that this sequence satisfies a familiar recurrence relation, an=anβˆ’1+anβˆ’2, but unlike the Fibonacci sequence, here the initial terms are a1=3 and a2=5. Is this appearance deceiving? Can we explain why this sequence should satisfy this recurrence?

Activity133

Explain why an satisfies the recurrence an=anβˆ’1+anβˆ’2. You will need to use the graphs Pn, Pnβˆ’1 and Pnβˆ’2 and their independent sets to do this. Show how you can β€œfind” the independent sets of Pnβˆ’1 and Pnβˆ’2 among the independent set of Pn (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 nth 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 an be the number of subsets of [n]. Find a recurrence relation for the sequence (an)nβ‰₯0. 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 kn be the number of edges in the complete graph Kn. Find a recurrence relation for the sequence (kn)nβ‰₯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 bn be the number of bijections from an n-element set to and n-element set. Find a recurrence relation for the sequence (bn)nβ‰₯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 mn 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 mn.

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 rn 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

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.

Hint2

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Γ—1 squares and 1Γ—2 dominoes. You wish to use these to tile a 1Γ—n path. For n=4, some examples of different paths are ssss, ssd, sds, dss, dd (in fact, these are all 5 of the possible paths).

(a)

Let an be the number of ways to tile the 1Γ—n path. Find a recurrence relation for the sequence (an)nβ‰₯1, 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 bn count the number of paths you can tile. Find an justify a recurrence relation for (bn)nβ‰₯1.

Activity140

Let cn be the number of independent sets of vertices in the cycle Cn. For consistency, label the vertices of Cn with the integers 1,2,…,n and assume E={(i,i+1):1≀i<n}βˆͺ{(n,1)}. Find a recurrence relation for (cn)nβ‰₯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.

Figure2.4.1The five triangulations of a convex pentagon.

Let tn be the number of triangulations. Find a recurrence relation for (tn)nβ‰₯3. 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 (an)nβ‰₯1 which satisfies the recurrence relation an=βˆ‘nβˆ’1i=1ai. 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 (an)n≀0 satisfy an=anβˆ’1+3 with a0=2. For example, an 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 an 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 (an)n≀0 satisfy an=3anβˆ’1 with a0=2. For example, an 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 an 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 (an)nβ‰₯1, we can form the sequence of partial sums (bn)nβ‰₯1 given by bn=βˆ‘ni=1an. That is, bn tells you what you get if you add up the first n terms of (an).

(a)

In general, what is a recurrence relation for (bn)?

Hint

If you have calculated \(b_{n-1}\text{,}\) what do you need to do to get \(b_n\text{?}\)

(b)

If (an)nβ‰₯1 is the sequence 1,3,5,7,9,…, find the sequence of partial sums bn.

(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 nth 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 nth 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).