Problem 87
How is the number of subsets of an \(n\)-element set related to the number of subsets of an \((n - 1)\)-element set? Prove that you are correct.
Hint
Remember, a subset of \([n]\) either does or doesn't contain \(n\text{.}\)
Section 2.2 Recurrence Relations
¶Problem 88
Explain why it is that the number of bijections from an \(n\)-element set to an \(n\)-element set is equal to \(n\) times the number of bijections from an \((n-1)\)-element subset to an \((n-1)\)-element set. What does this have to do with Problem 27?
We can summarize these observations as follows. If \(s_n\) stands for the number of subsets of an \(n\)-element set, then
\begin{equation}
s_n =2s_{n-1},\label{subsetequation}\tag{2.1}
\end{equation}
and if \(b_n\) stands for the number of bijections from an \(n\)-element set to an \(n\)-element set, then
\begin{equation}
b_n =
nb_{n-1}.\label{bijectionequation}\tag{2.2}
\end{equation}
Equations (2.1) and (2.2) are examples of recurrence equations or recurrence relations. A recurrence relation or simply a recurrence is an equation that expresses the \(n\)th term of a sequence \(a_n\) in terms of values of \(a_i\) for \(i\lt n\text{.}\) Thus Equations (2.1) and (2.2) are examples of recurrences.
Subsection 2.2.1 Examples of recurrence relations
¶Other examples of recurrences are
\begin{equation}
a_n = a_{n-1} +
7,\label{arithmeticexample}\tag{2.3}
\end{equation}
\begin{equation}
a_n =3a_{n-1} + 2^n,\label{geometricdriven}\tag{2.4}
\end{equation}
\begin{equation}
a_n = a_{n-1} + 3a_{n-2},\mbox{
and}\label{secondorderlinear}\tag{2.5}
\end{equation}
\begin{equation}
a_n= a_1a_{n-1} + a_2a_{n-2}+\cdots +
a_{n-1}a_1.\label{Catalan-recurrence}\tag{2.6}
\end{equation}
A solution to a recurrence relation is a sequence that satisfies the recurrence relation. Thus a solution to Recurrence (2.1) is \(s_n =2^n\text{.}\) Note that \(s_n=17\cdot2^n\) and \(s_n=-13\cdot2^n\) are also solutions to Recurrence (2.1). What this shows is that a recurrence can have infinitely many solutions. In a given problem, there is generally one solution that is of interest to us. For example, if we are interested in the number of subsets of a set, then the solution to Recurrence (2.1) that we care about is \(s_n=2^n\text{.}\) Notice this is the only solution we have mentioned that satisfies \(s_0=1\text{.}\)
Problem 89
Show that there is only one solution to Recurrence (2.1) that satisfies \(s_0=1\text{.}\)
Problem 90
A first-order recurrence relation is one which expresses \(a_n\) in terms of \(a_{n-1}\) and other functions of \(n\text{,}\) but which does not include any of the terms \(a_i\) for \(i\lt n-1\) in the equation.
(a)
Which of the recurrences (2.1) through (2.6) are first order recurrences?
(b)
Show that there is one and only one sequence \(a_n\) that is defined for every nonnegative integer \(n\text{,}\) satisfies a given first order recurrence, and satisfies \(a_0=a\) for some fixed constant \(a\text{.}\)
Hint
A first order recurrence for \(a_n\) gives us \(a_n\) as a function of \(a_{n-1}\text{.}\)
Problem 91
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.)
Hint
Suppose you already knew the number of moves needed to solve the puzzle with \(n-1\)rings.
Problem 92
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?
Hint 1
Hint 2
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.
Subsection 2.2.2 Arithmetic Series (optional)
¶Problem 93
A child puts away two dollars from her allowance each week. If she starts with twenty dollars, give a recurrence for the amount \(a_n\) of money she has after \(n\) weeks and find out how much money she has at the end of \(n\) weeks.
Problem 94
A sequence that satisfies a recurrence of the form \(a_n=a_{n-1} +c\) is called an arithmetic progression. Find a formula in terms of the initial value \(a_0\) and the common difference \(c\) for the term \(a_n\) in an arithmetic progression and prove you are right.
Problem 95
A person who is earning $50,000 per year gets a raise of $3000 a year for \(n\) years in a row. Find a recurrence for the amount \(a_n\) of money the person earns over \(n+1\) years. What is the total amount of money that the person earns over a period of \(n+1\) years? (In \(n+1\) years, there are \(n\) raises.)
Problem 96
An arithmetic series is a sequence \(s_n\) equal to the sum of the terms \(a_0\) through \(a_n\) of of an arithmetic progression. Find a recurrence for the sum \(s_n\) of an arithmetic progression with initial value \(a_0\) and common difference \(c\) (using the language of Problem 94). Find a formula for general term \(s_n\) of an arithmetic series.
Subsection 2.2.3 First order linear recurrences
¶Recurrences such as those in Equations (2.1) through (2.5) are called linear recurrences, as are the recurrences of Problems 91 and Problem 92. A linear recurrence is one in which \(a_n\) is expressed as a sum of functions of \(n\) times values of (some of the terms) \(a_i\) for \(i\lt n\) plus (perhaps) another function (called the driving function) of \(n\text{.}\) A linear equation is called homogeneous if the driving function is zero (or, in other words, there is no driving function). It is called a constant coefficient linear recurrence if the functions that are multiplied by the \(a_i\) terms are all constants (but the driving function need not be constant).
Problem 97
Classify the recurrences in Equations (2.1) through (2.5) and Problems 91 and Problem 92 according to whether or not they are constant coefficient, and whether or not they are homogeneous.
Problem 98
As you can see from Problem 97 some interesting sequences satisfy first order linear recurrences, including many that have constant coefficients, have constant driving term, or are homogeneous. Find a formula in terms of \(b\text{,}\) \(d\text{,}\) \(a_0\) and \(n\) for the general term \(a_n\) of a sequence that satisfies a constant coefficient first order linear recurrence \(a_n = ba_{n-1} + d\) and prove you are correct. If your formula involves a summation, try to replace the summation by a more compact expression.
Hint
You might try working out the cases \(n=2,3,4\) and then look for a pattern. Alternately, you could write \(a_{n-1}=b a_{n-2} + d\text{,}\) substitute the right hand side of this expression into \(a_{n}=b a_{n-1} + d\) to get a recurrence involving only \(a_{n-2}\) , and then repeat a similar process with \(a_{n-2}\) and perhaps \(a_{n-3}\) and see a pattern that is developing.
Subsection 2.2.4 Geometric Series
¶A sequence that satisfies a recurrence of the form \(a_n=ba_{n-1}\) is called a geometric progression. Thus the sequence satisfying Equation (2.1), the recurrence for the number of subsets of an \(n\)-element set, is an example of a geometric progression. From your solution to Problem 98, a geometric progression has the form \(a_n=a_0b^n\text{.}\) In your solution to Problem 98 you may have had to deal with the sum of a geometric progression in just slightly different notation, namely \(\sum_{i=0}^{n-1}db^i\text{.}\) A sum of this form is called a (finite) geometric series.
Problem 99
Do this problem only if your final answer (so far) to Problem 98 contained the sum \(\sum_{i=0}^{n-1}db^i\text{.}\)
(a)
Expand \((1-x)(1+x)\text{.}\) Expand \((1-x)(1+x+x^2)\text{.}\) Expand \((1-x)(1+x+x^2+x^3)\text{.}\)
(b)
What do you expect \((1-b)\sum_{i=0}^{n-1} db^i\) to be? What formula for \(\sum_{i=0}^{n-1}db^i\) does this give you? Prove that you are correct.
In Problem 98 and perhaps 99 you proved an important theorem.
Theorem 2.2.2
If \(b\not=1\) and \(a_n=ba_{n-1} +d\text{,}\) then \(\displaystyle a_n = a_0b^n + d\frac{1-b^n}{1-b}\text{.}\) If \(b=1\text{,}\) then, \(\displaystyle a_n = a_0 +nd\)
Corollary 2.2.3
If \(b\not=1\text{,}\) then \(\displaystyle \sum_{i=0}^{n-1}b^i = \frac{1-b^n}{1-b}\text{.}\) If \(b=1\text{,}\) \(\displaystyle \sum_{i=0}^{n-1}b^i =n\text{.}\)