Section 2.1 Describing Sequences
Investigate!
You have a large collection of \(1\times 1\) squares and \(1\times 2\) dominoes. You want to arrange these to make a \(1 \times 15\) strip. How many ways can you do this?
Start by collecting data. How many length \(1\times 1\) strips can you make? How many \(1\times 2\) strips? How many \(1\times 3\) strips? And so on.
How are the \(1\times 3\) and \(1 \times 4\) strips related to the \(1\times 5\) strips?
How many \(1\times 15\) strips can you make?
What if I asked you to find the number of \(1\times 1000\) strips? Would the method you used to calculate the number fo \(1 \times 15\) strips be helpful?
A sequence is simply an ordered list of numbers. For example, here is a sequence: 0, 1, 2, 3, 4, 5, …. This is different from the set \(\N\) because, while the sequence is a complete list of every element in the set of natural numbers, in the sequence we very much care what order the numbers come in. For this reason, when we use variables to represent terms in a sequence they will look like this:
\begin{equation*}
a_0, a_1, a_2, a_3, \ldots\text{.}
\end{equation*}
To refer to the entire sequence at once, we will write \((a_n)_{n\in\N}\) or \((a_n)_{n\ge 0}\text{,}\) or sometimes if we are being sloppy, just \((a_n)\) (in which case we assume we start the sequence with \(a_0\)).
We might replace the \(a\) with another letter, and sometimes we omit \(a_0\text{,}\) starting with \(a_1\text{,}\) in which case we would use \((a_n)_{n \ge 1}\) to refer to the sequence as a whole. The numbers in the subscripts are called indices (the plural of index).
While we often just think of a sequence as an ordered list of numbers, it is really a type of function. Specifically, the sequence \((a_n)_{n\ge 0}\) is a function with domain \(\N\) where \(a_n\) is the image of the natural number \(n\text{.}\) Later we will manipulate sequences in much the same way you have manipulated functions in algebra or calculus. We can shift a sequence up or down, add two sequences, or ask for the rate of change of a sequence. These are done exactly as you would for functions.
That said, while keeping the rigorous mathematical definition in mind is helpful, we often describe sequences by writing out the first few terms.
Example 2.1.1.
Can you find the next term in the following sequences?
\(\displaystyle 7,7,7,7,7, \ldots\)
\(\displaystyle 3, -3, 3, -3, 3, \ldots\)
\(\displaystyle 1, 5, 2, 10, 3, 15, \ldots\)
\(\displaystyle 1, 2, 4, 8, 16, 32, \ldots\)
\(\displaystyle 1, 4, 9, 16, 25, 36, \ldots\)
\(\displaystyle 1, 2, 3, 5, 8, 13, 21, \ldots\)
\(\displaystyle 1, 3, 6, 10, 15, 21, \ldots\)
\(\displaystyle 2, 3, 5, 7, 11, 13, \ldots\)
\(\displaystyle 3, 2, 1, 0, -1, \ldots\)
\(\displaystyle 1, 1, 2, 6, \ldots\)
Solution.
No you cannot. You might guess that the next terms are:
\(\displaystyle 7\)
\(\displaystyle -3\)
\(\displaystyle 4\)
64
49
34
28
17
\(\displaystyle -2\)
\(\displaystyle 24\)
In fact, those are the next terms of the sequences I had in mind when I made up the example, but there is no way to be sure they are correct.
Still, we will often do this. Given the first few terms of a sequence, we can ask what the pattern in the sequence suggests the next terms are.
Given that no number of initial terms in a sequence is enough to say for certain which sequence we are dealing with, we need to find another way to specify a sequence. We consider two ways to do this:
Closed formula.
A closed formula for a sequence \((a_n)_{n\in\N}\) is a formula for \(a_n\) using a fixed finite number of operations on \(n\text{.}\) This is what you normally think of as a formula in \(n\text{,}\) just as if you were defining a function in terms of \(n\) (because that is exactly what you are doing).
Recursive definition.
A recursive definition (sometimes called an inductive definition) for a sequence \((a_n)_{n\in\N}\) consists of a recurrence relation : an equation relating a term of the sequence to previous terms (terms with smaller index) and an initial condition: a list of a few terms of the sequence (one less than the number of terms in the recurrence relation).
It is easier to understand what is going on here with an example:
Example 2.1.2.
Here are a few closed formulas for sequences:
Note in each formula, if you are given \(n\text{,}\) you can calculate \(a_n\) directly: just plug in \(n\text{.}\) For example, to find \(a_3\) in the second sequence, just compute \(a_3 = \frac{3(3+1)}{2} = 6\text{.}\)
Here are a few recursive definitions for sequences:
\(a_n = 2a_{n-1}\) with \(a_0 = 1\text{.}\)
\(a_n = 2a_{n-1}\) with \(a_0 = 27\text{.}\)
\(a_n = a_{n-1} + a_{n-2}\) with \(a_0 = 0\) and \(a_1 = 1\text{.}\)
In these formulas, if you are given \(n\text{,}\) you cannot calculate \(a_n\) directly, you first need to find \(a_{n-1}\) (or \(a_{n-1}\) and \(a_{n-2}\)). In the second sequence, to find \(a_3\) you would take \(2a_2\text{,}\) but to find \(a_2 = 2a_1\) we would need to know \(a_1 = 2a_0\text{.}\) We do know this, so we could trace back through these equations to find \(a_1 = 54\text{,}\) \(a_2 = 108\) and finally \(a_3 = 216\text{.}\)
You might wonder why we would bother with recursive definitions for sequences. After all, it is harder to find \(a_n\) with a recursive definition than with a closed formula. This is true, but it is also harder to find a closed formula for a sequence than it is to find a recursive definition. So to find a useful closed formula, we might first find the recursive definition, then use that to find the closed formula.
This is not to say that recursive definitions aren’t useful in finding \(a_n\text{.}\) You can always calculate \(a_n\) given a recursive definition, it might just take a while.
Example 2.1.3.
Find \(a_6\) in the sequence defined by \(a_n = 2a_{n-1} - a_{n-2}\) with \(a_0 = 3\) and \(a_1 = 4\text{.}\)
Solution.
We know that \(a_6 = 2a_5 - a_4\text{.}\) So to find \(a_6\) we need to find \(a_5\) and \(a_4\text{.}\) Well
\begin{equation*}
a_5 = 2a_4 - a_3 \qquad \text{and} \qquad a_4 = 2a_3 - a_2\text{,}
\end{equation*}
so if we can only find \(a_3\) and \(a_2\) we would be set. Of course
\begin{equation*}
a_3 = 2a_2 - a_1 \qquad \text{and} \qquad a_2 = 2a_1 - a_0\text{,}
\end{equation*}
so we only need to find \(a_1\) and \(a_0\text{.}\) But we are given these. Thus
\begin{align*}
a_0 \amp = 3\\
a_1 \amp = 4\\
a_2 \amp = 2\cdot 4 - 3 = 5\\
a_3 \amp = 2\cdot 5 - 4 = 6\\
a_4 \amp = 2\cdot 6 - 5 = 7\\
a_5 \amp = 2\cdot 7 - 6 = 8\\
a_6 \amp = 2\cdot 8 - 7 = 9\text{.}
\end{align*}
Note that now we can guess a closed formula for the \(n\)th term of the sequence: \(a_n = n+3\text{.}\) To be sure this will always work, we could plug in this formula into the recurrence relation:
\begin{align*}
2a_{n-1} - a_{n-2} \amp = 2((n-1) + 3) - ((n-2) + 3)\\
\amp = 2n + 4 - n - 1\\
\amp = n + 3\\
\amp = a_n\text{.}
\end{align*}
That is not quite enough though, since there can be multiple closed formulas that satisfy the same recurrence relation; we must also check that our closed formula agrees on the initial terms of the sequence. Since \(a_0 = 0 + 3 = 3\) and \(a_1 = 1+3 = 4\) are the correct initial conditions, we can now conclude we have the correct closed formula.
Finding closed formulas, or even recursive definitions, for sequences is not trivial. There is no one method for doing this. Just as in evaluating integrals or solving differential equations, it is useful to have a bag of tricks you can apply, but sometimes there is no easy answer.
One useful method is to relate a given sequence to another sequence for which we already know the closed formula. To do this, we need a few “known sequences” to compare mystery sequences to. Here are a few that are good to know. We will verify the formulas for these in the coming sections.
Common Sequences.
- \(1, 4, 9, 16, 25, \ldots\)
The square numbers. The sequence \((s_n)_{n \ge 1}\) has closed formula \(s_n = n^2\)
- \(1, 3, 6, 10, 15, 21, \ldots\)
The triangular numbers. The sequence \((T_n)_{n \ge 1}\) has closed formula \(T_n = \frac{n(n+1)}{2}\text{.}\)
- \(1, 2, 4, 8, 16, 32,\ldots\)
The powers of 2. The sequence \((a_n)_{n \ge 0}\) with closed formula \(a_n = 2^n\text{.}\)
- \(1, 1, 2, 3, 5, 8, 13, \ldots\)
The Fibonacci numbers (or Fibonacci sequence), defined recursively by \(F_n = F_{n-1} + F_{n-2}\) with \(F_1 = F_2 = 1\text{.}\)
Example 2.1.4.
Use the formulas \(T_n = \frac{n(n+1)}{2}\) and \(a_n = 2^n\) to find closed formulas that agree with the following sequences. Assume each first term corresponds to \(n=0\text{.}\)
\((b_n)\text{:}\) \(1, 2, 4, 7, 11, 16, 22, \ldots \text{.}\)
\((c_n)\text{:}\) \(3, 5, 9, 17, 33,\ldots \text{.}\)
\((d_n)\text{:}\) \(0, 2, 6, 12, 20, 30, 42,\ldots \text{.}\)
\((e_n)\text{:}\) \(3, 6, 10, 15, 21, 28, \ldots\text{.}\)
\((f_n)\text{:}\) \(0, 1, 3, 7, 15, 31, \ldots \text{.}\)
\((g_n)\) \(3, 6, 12, 24, 48, \ldots \text{.}\)
\((h_n)\text{:}\) \(6, 10, 18, 34, 66, \ldots \text{.}\)
\((j_n)\text{:}\) \(15, 33, 57, 87, 123, \ldots\text{.}\)
Solution.
We wish to compare these sequences to the triangular numbers \((0, 1, 3, 6, 10, 15, 21,\ldots)\text{,}\) when we start with \(n=0\text{,}\) and the powers of 2: \((1, 2, 4, 8, 16, \ldots)\text{.}\)
\((1, 2, 4, 7, 11, 16, 22, \ldots)\text{.}\) Note that if subtract 1 from each term, we get the sequence \((T_n)\text{.}\) So we have \(b_n = T_n + 1\text{.}\) Therefore a closed formula is \(b_n = \frac{n(n+1)}{2} + 1\text{.}\) A quick check of the first few \(n\) confirms we have it right.
\((3, 5, 9, 17, 33, \ldots )\text{.}\) Each term in this sequence is one more than a power of 2, so we might guess the closed formula is \(c_n = a_n+1 = 2^n + 1\text{.}\) If we try this though, we get \(c_0 = 2^0 + 1 = 2\) and \(c_1 = 2^1 + 1 = 3\text{.}\) We are off because the indices are shifted. What we really want is \(c_n = a_{n+1}+1\) giving \(c_n = 2^{n+1} + 1\text{.}\)
(\(0, 2, 6, 12, 20, 30, 42,\ldots \)). Notice that all these terms are even. What happens if we factor out a 2? We get \((T_n)\text{!}\) More precisely, we find that \(d_n/2 = T_n\text{,}\) so this sequence has closed formula \(d_n = n(n+1)\text{.}\)
\((3, 6, 10, 15, 21, 28, \ldots)\text{.}\) These are all triangular numbers. However, we are starting with 3 as our initial term instead of as our third term. So if we could plug in 2 instead of 0 into the formula for \(T_n\text{,}\) we would be set. Therefore the closed formula is \(e_n = \frac{(n+2)(n+3)}{2}\) (where \(n+3\) came from \((n+2)+1\)). Thinking about sequences as functions, we are doing a horizontal shift by 2: \(e_n = T_{n+2}\) which would cause the graph to shift 2 units to the left.
\((0, 1, 3, 7, 15, 31, \ldots )\text{.}\) Try adding 1 to each term and we get powers of 2. You might guess this because each term is a little more than twice the previous term (the powers of 2 are exactly twice the previous term). Closed formula: \(f_n = 2^{n} - 1\text{.}\)
\((3, 6, 12, 24, 48, \ldots )\text{.}\) These numbers are also doubling each time, but are also all multiples of 3. Dividing each by 3 gives 1, 2, 4, 8, …. Aha. We get the closed formula \(g_n = 3\cdot 2^{n}\text{.}\)
\((6, 10, 18, 34, 66, \ldots )\text{.}\) To get from one term to the next, we almost double each term. So maybe we can relate this back to \(2^n\text{.}\) Yes, each term is 2 more than a power of 2. So we get \(h_n = 2^{n+2} + 2\) (the \(n+2\) is because the first term is 2 more than \(2^2\text{,}\) not \(2^0\)). Alternatively, we could have related this sequence to the second sequence in this example: starting with 3, 5, 9, 17, … we see that this sequence is twice the terms from that sequence. That sequence had closed formula \(c_n = 2^{n+1} + 1\text{.}\) Our sequence here would be twice this, so \(h_n = 2(2^n + 1)\text{,}\) which is the same as we got before.
\((15, 33, 57, 87, 123, \ldots)\text{.}\) Try dividing each term by 3. That gives the sequence \(5, 11, 19, 29, 41,\ldots\text{.}\) Now add 1 to each term: \(6, 12, 20, 30, 42, \ldots\text{,}\) which is \((d_n)\) in this example, except starting with 6 instead of 0. So let’s start with the formula \(d_n= n(n+1)\text{.}\) To start with the 6, we shift: \((n+2)(n+3)\text{.}\) But this is one too many, so subtract 1: \((n+2)(n+3) - 1\text{.}\) That gives us our sequence, but divided by 3. So we want \(j_n = 3((n+2)(n+3) - 1)\text{.}\)
Partial sums.
Some sequences naturally arise as the sum of terms of another sequence.
Example 2.1.5.
Sam keeps track of how many push-ups she does each day of her “do lots of push-ups challenge.” Let \((a_n)_{n \ge 1}\) be the sequence that describes the number of push-ups done on the \(n\)th day of the challenge. The sequence starts
\begin{equation*}
3, 5, 6, 10, 9, 0, 12, \ldots\text{.}
\end{equation*}
Describe a sequence \((b_n)_{n \ge 1}\) that describes the total number of push-ups done by Sam after the \(n\)th day.
Solution.
We can find the terms of this sequence easily enough.
\begin{equation*}
3, 8, 14, 24, 33, 33, 45,\ldots\text{.}
\end{equation*}
Here \(b_1\) is just \(a_1\text{,}\) but then
\begin{equation*}
b_2 = 3+5 = a_1 + a_2\text{,}
\end{equation*}
\begin{equation*}
b_3 = 3+5+6 = a_1 + a_2 + a_3\text{,}
\end{equation*}
and so on.
There are a few ways we might describe \(b_n\) in general. We could do so recursively as,
\begin{equation*}
b_n = b_{n-1} + a_n\text{,}
\end{equation*}
since the total number of push-ups done after \(n\) days will be the number done after \(n-1\) days, plus the number done on day \(n\text{.}\)
For something closer to a closed formula, we could write
\begin{equation*}
b_n = a_1 + a_2 + a_3 + \cdots + a_n\text{,}
\end{equation*}
or the same thing using summation notation:
\begin{equation*}
b_n = \sum_{i=1}^n a_i\text{.}
\end{equation*}
However, note that these are not really closed formulas since even if we had a formula for \(a_n\text{,}\) we would still have an increasing number of computations to do as \(n\) increases.
Given any sequence \((a_n)_{n \in \N}\text{,}\) we can always form a new sequence \((b_n)_{n \in \N}\) by
\begin{equation*}
b_n = a_0 + a_1 + a_2 + \cdots + a_n\text{.}
\end{equation*}
Since the terms of \((b_n)\) are the sums of the initial part of the sequence \((a_n)\) ways call \((b_n)\) the sequence of partial sums of \((a_n)\). Soon we will see that it is sometimes possible to find a closed formula for \((b_n)\) from the closed formula for \((a_n)\text{.}\)
To simplify writing out these sums, we will often use notation like \(\d\sum_{k=1}^n a_k\text{.}\) This means add up the \(a_k\)’s where \(k\) changes from 1 to \(n\text{.}\)
Example 2.1.6.
Use \(\sum\) notation to rewrite the sums:
\(\displaystyle 1 + 2 + 3 + 4 + \cdots + 100\)
\(\displaystyle 1 + 2 + 4 + 8 + \cdots + 2^{50}\)
\(6 + 10 + 14 + \cdots + (4n - 2)\text{.}\)
Solution.
\(\displaystyle \d\sum_{k=1}^{100} k\)
\(\displaystyle \d\sum_{k=0}^{50} 2^k\)
\(\displaystyle \d\sum_{k=2}^{n} (4k -2)\)
If we want to multiply the \(a_k\) instead, we could write \(\d\prod_{k=1}^n a_k\text{.}\) For example, \(\d\prod_{k=1}^n k = n!\text{.}\)
Exercises Exercises
1.
2.
3.
Consider the sequence \((a_n)_{n \ge 1}\) that starts \(1, 3, 5, 7, 9, \ldots\) (i.e., the odd numbers in order).
Give a recursive definition and closed formula for the sequence.
Write out the sequence \((b_n)_{n \ge 2}\) of partial sums of \((a_n)\text{.}\) Write down the recursive definition for \((b_n)\) and guess at the closed formula.
Solution.
The recursive definition is \(a_n = a_{n-1} + 2\) with \(a_1 = 1\text{.}\) A closed formula is \(a_n = 2n-1\text{.}\)
The sequence of partial sums is \(1, 4, 9, 16, 25, 36, \ldots\text{.}\) A recursive definition is (as always) \(b_n = b_{n-1} + a_n\) which in this case is \(b_n = b_{n-1} + 2n-1\text{.}\) It appears that the closed formula is \(b_n = n^2\)
4.
The Fibonacci sequence is \(0, 1, 1, 2, 3, 5, 8, 13, \ldots\) (where \(F_0 = 0\)).
Write out the first few terms of the sequence of partial sums: \(0\text{,}\) \(0+1\text{,}\) \(0+1+1\text{,}\)…
Guess a formula for the sequence of partial sums expressed in terms of a single Fibonacci number. For example, you might say \(F_0 + F_1 + \cdots + F_n = 3F_{n-1}^2 + n\text{,}\) although that is definitely not correct.
Solution.
\(0, 1, 2, 4, 7, 12, 20, \ldots\text{.}\)
\(F_0 + F_1 + \cdots + F_n = F_{n+2} - 1\text{.}\)
5.
Consider the three sequences below. For each, find a recursive definition. How are these sequences related?
\(2, 4, 6, 10, 16, 26, 42, \ldots\text{.}\)
\(5, 6, 11, 17, 28, 45, 73, \ldots\text{.}\)
\(0, 0 , 0 , 0 , 0 , 0 , 0 ,\ldots\text{.}\)
Solution.
The sequences all have the same recurrence relation: \(a_n = a_{n-1} + a_{n-2}\) (the same as the Fibonacci numbers). The only difference is the initial conditions.
6.
Write out the first few terms of the sequence given by \(a_1 = 3\text{;}\) \(a_n = 2a_{n-1} + 4\text{.}\) Then find a recursive definition for the sequence \(10, 24, 52, 108, \ldots\text{.}\)
Solution.
\(3, 10, 24, 52, 108,\ldots\text{.}\) The recursive definition for \(10, 24, 52, \ldots\) is \(a_n = 2a_{n-1} + 4\) with \(a_1 = 10\text{.}\)
7.
Write out the first few terms of the sequence given by \(a_n = n^2 - 3n + 1\text{.}\) Then find a closed formula for the sequence (starting with \(a_1\)) \(0, 2, 6, 12, 20, \ldots\text{.}\)
Solution.
\(-1, -1, 1, 5, 11, 19,\ldots\) Thus the sequence \(0, 2, 6, 12, 20,\ldots\) has closed formula \(a_n = (n+1)^2 - 3(n+1) + 2\text{.}\)
8.
Show that \(a_n = 3\cdot 2^n + 7\cdot 5^n\) is a solution to the recurrence relation \(a_n = 7a_{n-1} - 10a_{n-2}\text{.}\) What would the initial conditions need to be for this to be the closed formula for the sequence?
Solution.
This closed formula would have \(a_{n-1} = 3\cdot 2^{n-1} + 7 \cdot 5^{n-1}\) and \(a_{n-2} = 3\cdot 2^{n-2} + 7 \cdot 5^{n-2}\text{.}\) Then we would have
\begin{align*}
7a_{n-1} - 10a_{n-2} = \amp 7(3\cdot 2^{n-1} + 7 \cdot 5^{n-1}) - 10(3\cdot 2^{n-2} + 7 \cdot 5^{n-2})\\
= \amp 21\cdot 2^{n-1} + 49 \cdot 5^{n-1} - 30\cdot 2^{n-2} - 70 \cdot 5^{n-2})\\
= \amp 21\cdot 2^{n-1} + 49 \cdot 5^{n-1} - 15\cdot 2^{n-1} - 14 \cdot 5^{n-1})\\
= \amp 6\cdot 2^{n-1} + 35 \cdot 5^{n-1}\\
= \amp 3\cdot 2^{n} + 7 \cdot 5^{n} = a_n\text{.}
\end{align*}
So the closed formula agrees with the recurrence relation. The closed formula has initial terms \(a_0 = 10\) and \(a_1 = 41\text{.}\)
9.
Show that \(a_n = 2^n - 5^n\) is also a solution to the recurrence relation \(a_n = 7a_{n-1} - 10a_{n-2}\text{.}\) What would the initial conditions need to be for this to be the closed formula for the sequence?
10.
Find a closed formula for the sequence with recursive definition \(a_n = 2a_{n-1} - a_{n-2}\) with \(a_1 = 1\) and \(a_2 = 2\text{.}\)
Hint.
You will want to write out the sequence, guess a closed formula, and then verify that you are correct.
11.
Give two different recursive definitions for the sequence with closed formula \(a_n = 3 + 2n\text{.}\) Prove you are correct. At least one of the recursive definitions should makes use of two previous terms and no constants.
Hint.
Write out the sequence, guess a recursive definition, and verify that the closed formula is a solution to that recursive definition.
12.
Use summation (\(\sum\)) or product (\(\prod\)) notation to rewrite the following.
\(2 + 4 + 6 + 8 + \cdots + 2n\text{.}\)
\(1 + 5 + 9 + 13 + \cdots + 425\text{.}\)
\(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{50}\text{.}\)
\(2 \cdot 4 \cdot 6 \cdot \cdots \cdot 2n\text{.}\)
\((\frac{1}{2})(\frac{2}{3})(\frac{3}{4})\cdots(\frac{100}{101})\text{.}\)
Solution.
\(\d\sum_{k=1}^n 2k\text{.}\)
\(\d\sum_{k=1}^{107} (1 + 4(k-1))\text{.}\)
\(\d\sum_{k=1}^{50} \frac{1}{k}\text{.}\)
\(\d\prod_{k=1}^n 2k\text{.}\)
\(\d\prod_{k=1}^{100} \frac{k}{k+1}\text{.}\)
13.
Expand the following sums and products. That is, write them out the long way.
\(\d\sum_{k=1}^{100} (3+4k)\text{.}\)
\(\d\sum_{k=0}^n 2^k\text{.}\)
\(\d\sum_{k=2}^{50}\frac{1}{(k^2 - 1)}\text{.}\)
\(\d\prod_{k=2}^{100}\frac{k^2}{(k^2-1)}\text{.}\)
\(\d\prod_{k=0}^n (2+3k)\text{.}\)
Solution.
\(\d\sum_{k=1}^{100} (3+4k) = 7 + 11 + 15 + \cdots + 403\text{.}\)
\(\d\sum_{k=0}^n 2^k = 1 + 2 + 4 + 8 + \cdots + 2^n\text{.}\)
\(\d\sum_{k=2}^{50}\frac{1}{(k^2 - 1)} = 1 + \frac{1}{3} + \frac{1}{8} + \frac{1}{15} + \cdots + \frac{1}{2499}\text{.}\)
\(\d\prod_{k=2}^{100}\frac{k^2}{(k^2-1)} = \frac{4}{3}\cdot\frac{9}{8}\cdot\frac{16}{15}\cdots\frac{10000}{9999}\text{.}\)
\(\d\prod_{k=0}^n (2+3k) = (2)(5)(8)(11)(14)\cdots(2+3n)\text{.}\)
14.
Suppose you draw \(n\) lines in the plane so that every pair of lines cross (no lines are parallel) and no three lines cross at the same point. This will create some number of regions in the plane, including some unbounded regions. Call the number of regions \(R_n\text{.}\) Find a recursive formula for the number of regions created by \(n\) lines, and justify why your recursion is correct.
Hint.
Try an example: when you draw the 4th line, it will cross three other lines, so will be divided into four segments, two of which are infinite. Each segment will divide a previous region into two.
15.
A ternary string is a sequence of 0’s, 1’s and 2’s. Just like a bit string, but with three symbols.
Let’s call a ternary string good provided it never contains a 2 followed immediately by a 0. Let \(G_n\) be the number of good strings of length \(n\text{.}\) For example, \(G_1 = 3\text{,}\) and \(G_2 = 8\) (since of the 9 ternary strings of length 2, only one is not good).
Find, with justification, a recursive formula for \(G_n\text{,}\) and use it to compute \(G_5\text{.}\)
Hint.
Consider three cases: the last digit is a 0, a 1, or a 2. Two of these should be easy to count, but strings ending in 0 cannot be proceeded by a 2, so require a little more work.
16.
Consider bit strings with length \(l\) and weight \(k\) (so strings of \(l\) 0’s and 1’s, including \(k\) 1’s). We know how to count the number of these for a fixed \(l\) and \(k\text{.}\) Now, we will count the number of strings for which the sum of the length and the weight is fixed. For example, let’s count all the bit strings for which \(l+k = 11\text{.}\)
Find examples of these strings of different lengths. What is the longest string possible? What is the shortest?
How many strings are there of each of these lengths. Use this to count the total number of strings (with sum 11).
The other approach: Let \(n = l+k\) vary. How many strings have sum \(n = 1\text{?}\) How many have sum \(n = 2\text{?}\) And so on. Find and explain a recurrence relation for the sequence \((a_n)\) which gives the number of strings with sum \(n\text{.}\)
Describe what you have found above in terms of Pascal’s Triangle. What pattern have you discovered?
17.
When bees play chess, they use a hexagonal board like the one shown below. The queen bee can move one space at a time either directly to the right or angled up-right or down-right (but can never move leftwards). How many different paths can the queen take from the top left hexagon to the bottom right hexagon? Explain your answer, and this relates to the previous question. (As an example, there are three paths to get to the second hexagon on the bottom row.)
Hint.
Think recursively, like you did in Pascal’s triangle.
18.
Let \(t_n\) denote the number of ways to tile a \(2\times n\) chessboard using \(1\times 2\) dominoes. Write out the first few terms of the sequence \((t_n)_{n \ge 1}\) and then give a recursive definition. Explain why your recursive formula is correct.
Hint.
There is only one way to tile a \(2 \times 1\) board, and two ways to tile a \(2\times 2\) board (you can orient the dominoes in two ways). In general, consider the two ways the domino covering the top left corner could be oriented.
