3.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:

$a sub 0, a sub 1, a sub 2, a sub 3, and so on$

. To refer to the entire sequence at once, we will write $open parenthesis a sub n close parenthesis sub n ∈ N$ or $open parenthesis a sub n close parenthesis sub n greater than or equal to 0$ , or sometimes if we are being sloppy, just $(a_{n})$ (in which case we assume we start the sequence with $a sub 0$ ).

We might replace the $a$ with another letter, and sometimes we omit $a sub 0$ , starting with $a sub 1$ , in which case we would use $open parenthesis a sub n close parenthesis sub n greater than or equal to 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 $open parenthesis a sub n close parenthesis sub n greater than or equal to 0$ is a function with domain $N$ where $a_{n}$ is the image of the natural number $n$ . 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 1

Can you find the next term in the following sequences?

$7, 7, 7, 7, 7, and so on$
$3, - 3, 3, - 3, 3, \dots$
$1, 5, 2, 10, 3, 15, and so on$
$1, 2, 4, 8, 16, 32, and so on$
$1, 4, 9, 16, 25, 36, and so on$
$1, 2, 3, 5, 8, 13, 21, and so on$
$1, 3, 6, 10, 15, 21, and so on$
$2, 3, 5, 7, 11, 13, and so on$
$3, 2, 1, 0, minus 1, and so on$
$1, 1, 2, 6, and so on$

No you cannot. You might guess that the next terms are:

$7$
$minus 3$
$4$
64
49
34
28
17
$minus 2$
$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:

It is easier to understand what is going on here with an example:

Example 2

Here are a few closed formulas for sequences:

$a_{n} = n^{2}$ .
$a_{n} = \frac{n (n + 1)}{2}$ .
$a_{n} = \frac{{(\frac{1 + \sqrt{5}}{2})}^{n} - {(\frac{1 - \sqrt{5}}{2})}^{- n}}{\sqrt{5}}$ .

Note in each formula, if you are given $n$ , you can calculate $a_{n}$ directly: just plug in $n$ . For example, to find $a sub 3$ in the second sequence, just compute $a_{3} = \frac{3 (3 + 1)}{2} = 6$ .

Here are a few recursive definitions for sequences:

$a_{n} = 2 a_{n - 1}$ with $a sub 0 equals 1$ .
$a_{n} = 2 a_{n - 1}$ with $a sub 0 equals 27$ .
$a_{n} = a_{n - 1} + a_{n - 2}$ with $a sub 0 equals 0$ and $a sub 1 equals 1$ .

In these formulas, if you are given $n$ , you cannot calculate $a_{n}$ directly, you first need to find $a sub n minus 1$ (or $a sub n minus 1$ and $a sub n minus 2$ ). In the second sequence, to find $a sub 3$ you would take $2 a sub 2$ , but to find $a sub 2 equals 2 a sub 1$ we would need to know $a sub 1 equals 2 a sub 0$ . We do know this, so we could trace back through these equations to find $a sub 1 equals 54$ , $a sub 2 equals 108$ and finally $a sub 3 equals 216$ .

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}$ . You can always calculate $a_{n}$ given a recursive definition, it might just take a while.

Example 3

Find $a sub 6$ in the sequence defined by $a_{n} = 2 a_{n - 1} - a_{n - 2}$ with $a sub 0 equals 3$ and $a sub 1 equals 4$ .

We know that $a_{6} = 2 a_{5} - a_{4}$ . So to find $a sub 6$ we need to find $a sub 5$ and $a sub 4$ . Well

$a_{5} = 2 a_{4} - a_{3} and a_{4} = 2 a_{3} - a_{2}$

, so if we can only find $a sub 3$ and $a sub 2$ we would be set. Of course

$a_{3} = 2 a_{2} - a_{1} and a_{2} = 2 a_{1} - a_{0}$

, so we only need to find $a sub 1$ and $a sub 0$ . But we are given these. Thus

$\begin{aligned} a_{0} & = 3 \\ a_{1} & = 4 \\ a_{2} & = 2 \cdot 4 - 3 = 5 \\ a_{3} & = 2 \cdot 5 - 4 = 6 \\ a_{4} & = 2 \cdot 6 - 5 = 7 \\ a_{5} & = 2 \cdot 7 - 6 = 8 \\ a_{6} & = 2 \cdot 8 - 7 = 9 \end{aligned}$

Note that now we can guess a closed formula for the $n$ th term of the sequence: $a_{n} = n + 3$ . To be sure this will always work, we could plug in this formula into the recurrence relation:

$\begin{aligned} 2 a_{n - 1} - a_{n - 2} & = 2 ((n - 1) + 3) - ((n - 2) + 3) \\ = 2 n + 4 - n - 1 \\ = n + 3 \\ = a_{n} \end{aligned}$

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.

Summary

Common Sequences

$1, 4, 9, 16, 25, and so on$
The square numbers. The sequence $open parenthesis s sub n close parenthesis sub n greater than or equal to 1$ has closed formula $s_{n} = n^{2}$
$1, 3, 6, 10, 15, 21, and so on$
The triangular numbers. The sequence $open parenthesis T sub n close parenthesis sub n greater than or equal to 1$ has closed formula $T_{n} = \frac{n (n + 1)}{2}$ .
$1, 2, 4, 8, 16, 32, and so on$
The powers of 2. The sequence $open parenthesis a sub n close parenthesis sub n greater than or equal to 0$ with closed formula $a_{n} = 2^{n}$ .
$1, 1, 2, 3, 5, 8, 13, and so on$
The Fibonacci numbers (or Fibonacci sequence), defined recursively by $F_{n} = F_{n - 1} + F_{n - 2}$ with $F_{1} = F_{2} = 1$ .

Example 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 equals 0$ .

$(b_{n})$ : $1, 2, 4, 7, 11, 16, 22, and so on$ .
$(c_{n})$ : $3, 5, 9, 17, 33, and so on$ .
$(d_{n})$ : $0, 2, 6, 12, 20, 30, 42, and so on$ .
$(e_{n})$ : $3, 6, 10, 15, 21, 28, and so on$ .
$(f_{n})$ : $0, 1, 3, 7, 15, 31, and so on$ .
$(g_{n})$ $3, 6, 12, 24, 48, and so on$ .
$(h_{n})$ : $6, 10, 18, 34, 66, and so on$ .
$(j_{n})$ : $15, 33, 57, 87, 123, and so on$ .

We wish to compare these sequences to the triangular numbers $open parenthesis 0, 1, 3, 6, 10, 15, 21, and so on close parenthesis$ , when we start with $n equals 0$ , and the powers of 2: $open parenthesis 1, 2, 4, 8, 16, and so on close parenthesis$ .

$open parenthesis 1, 2, 4, 7, 11, 16, 22, and so on close parenthesis$ . Note that if subtract 1 from each term, we get the sequence $(T_{n})$ . So we have $b_{n} = T_{n} + 1$ . Therefore a closed formula is $b_{n} = \frac{n (n + 1)}{2} + 1$ . A quick check of the first few $n$ confirms we have it right.
$open parenthesis 3, 5, 9, 17, 33, and so on close parenthesis$ . 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$ . If we try this though, we get $c_{0} = 2^{0} + 1 = 2$ and $c_{1} = 2^{1} + 1 = 3$ . 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$ .
( $0, 2, 6, 12, 20, 30, 42, and so on$ ). Notice that all these terms are even. What happens if we factor out a 2? We get $(T_{n})$ ! More precisely, we find that $d sub n / 2 equals T sub n$ , so this sequence has closed formula $d_{n} = n (n + 1)$ .
$open parenthesis 3, 6, 10, 15, 21, 28, and so on close parenthesis$ . 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}$ , we would be set. Therefore the closed formula is $e_{n} = \frac{(n + 2) (n + 3)}{2}$ (where $n plus 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.
$open parenthesis 0, 1, 3, 7, 15, 31, and so on close parenthesis$ . 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$ .
$open parenthesis 3, 6, 12, 24, 48, and so on close parenthesis$ . 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}$ .
$open parenthesis 6, 10, 18, 34, 66, and so on close parenthesis$ . To get from one term to the next, we almost double each term. So maybe we can relate this back to $2 to the power n$ . Yes, each term is 2 more than a power of 2. So we get $h_{n} = 2^{n + 2} + 2$ (the $n plus 2$ is because the first term is 2 more than $2 squared$ , not $2 to the power 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$ . Our sequence here would be twice this, so $h_{n} = 2 (2^{n} + 1)$ , which is the same as we got before.
$open parenthesis 15, 33, 57, 87, 123, and so on close parenthesis$ . Try dividing each term by 3. That gives the sequence $5, 11, 19, 29, 41, and so on$ . Now add 1 to each term: $6, 12, 20, 30, 42, and so on$ , 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)$ . To start with the 6, we shift: $(n + 2) (n + 3)$ . But this is one too many, so subtract 1: $(n + 2) (n + 3) - 1$ . That gives us our sequence, but divided by 3. So we want $j_{n} = 3 ((n + 2) (n + 3) - 1)$ .

Partial sums

Some sequences naturally arise as the sum of terms of another sequence.

Example 5

Sam keeps track of how many push-ups she does each day of her “do lots of push-ups challenge.” Let $open parenthesis a sub n close parenthesis sub n greater than or equal to 1$ be the sequence that describes the number of push-ups done on the $n$ th day of the challenge. The sequence starts

$3, 5, 6, 10, 9, 0, 12, and so on$

. Describe a sequence $open parenthesis b sub n close parenthesis sub n greater than or equal to 1$ that describes the total number of push-ups done by Sam after the $n$ th day.

We can find the terms of this sequence easily enough.

$3, 8, 14, 24, 33, 33, 45, and so on$

. Here $b sub 1$ is just $a sub 1$ , but then

$b_{2} = 3 + 5 = a_{1} + a_{2}$

$b_{3} = 3 + 5 + 6 = a_{1} + a_{2} + a_{3}$

, and so on.

There are a few ways we might describe $b_{n}$ in general. We could do so recursively as,

$b_{n} = b_{n - 1} + a_{n}$

, since the total number of push-ups done after $n$ days will be the number done after $n minus 1$ days, plus the number done on day $n$ .

For something closer to a closed formula, we could write

$b_{n} = a_{1} + a_{2} + a_{3} + \dots + a_{n}$

, or the same thing using summation notation:

$b_{n} = \sum_{i = 1}^{n} a_{i}$

. However, note that these are not really closed formulas since even if we had a formula for $a_{n}$ , we would still have an increasing number of computations to do as $n$ increases.

Given any sequence $open parenthesis a sub n close parenthesis sub n ∈ N$ , we can always form a new sequence $open parenthesis b sub n close parenthesis sub n ∈ N$ by

$b_{n} = a_{0} + a_{1} + a_{2} + \dots + a_{n}$

. 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})$ .

To simplify writing out these sums, we will often use notation like $∑ k equals 1 n a sub k$ . This means add up the $a_{k}$ 's where $k$ changes from 1 to $n$ .

If we want to multiply the $a_{k}$ instead, we could write $∏ k equals 1 n a sub k$ . For example, $\prod_{k = 1}^{n} k = n!$ .

Consider the sequence $open parenthesis a sub n close parenthesis sub n greater than or equal to 1$ that starts $1, 3, 5, 7, 9, and so on$ (i.e., the odd numbers in order).

Give a recursive definition and closed formula for the sequence.
Write out the sequence $open parenthesis b sub n close parenthesis sub n greater than or equal to 2$ of partial sums of $(a_{n})$ . Write down the recursive definition for $(b_{n})$ and guess at the closed formula.

The recursive definition is $a_{n} = a_{n - 1} + 2$ with $a sub 1 equals 1$ . A closed formula is $a_{n} = 2 n - 1$ .
The sequence of partial sums is $1, 4, 9, 16, 25, 36, and so on$ . A recursive definition is (as always) $b_{n} = b_{n - 1} + a_{n}$ which in this case is $b_{n} = b_{n - 1} + 2 n - 1$ . It appears that the closed formula is $b_{n} = n^{2}$

The Fibonacci sequence is $0, 1, 1, 2, 3, 5, 8, 13, and so on$ (where $F sub 0 equals 0$ ).

Write out the first few terms of the sequence of partial sums: $0$ , $0 plus 1$ , $0 + 1 + 1$ ,…
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} + \dots + F_{n} = 3 F_{n - 1}^{2} + n$ , although that is definitely not correct.

$0, 1, 2, 4, 7, 12, 20, and so on$ .
$F_{0} + F_{1} + \dots + F_{n} = F_{n + 2} - 1$ .

Consider the three sequences below. For each, find a recursive definition. How are these sequences related?

$2, 4, 6, 10, 16, 26, 42, and so on$ .
$5, 6, 11, 17, 28, 45, 73, and so on$ .
$0, 0, 0, 0, 0, 0, 0, and so on$ .

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.

Write out the first few terms of the sequence given by $a sub 1 equals 3$ ; $a_{n} = 2 a_{n - 1} + 4$ . Then find a recursive definition for the sequence $10, 24, 52, 108, and so on$ .

$3, 10, 24, 52, 108, and so on$ . The recursive definition for $10, 24, 52, and so on$ is $a_{n} = 2 a_{n - 1} + 4$ with $a sub 1 equals 10$ .

Write out the first few terms of the sequence given by $a_{n} = n^{2} - 3 n + 1$ . Then find a closed formula for the sequence (starting with $a sub 1$ ) $0, 2, 6, 12, 20, and so on$ .

$- 1, - 1, 1, 5, 11, 19, \dots$ Thus the sequence $0, 2, 6, 12, 20, and so on$ has closed formula $a_{n} = (n + 1)^{2} - 3 (n + 1) + 2$ .

Show that $a_{n} = 3 \cdot 2^{n} + 7 \cdot 5^{n}$ is a solution to the recurrence relation $a_{n} = 7 a_{n - 1} - 10 a_{n - 2}$ . What would the initial conditions need to be for this to be the closed formula for the sequence?

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}$ . Then we would have

$\begin{aligned} 7 a_{n - 1} - 10 a_{n - 2} = & 7 (3 \cdot 2^{n - 1} + 7 \cdot 5^{n - 1}) - 10 (3 \cdot 2^{n - 2} + 7 \cdot 5^{n - 2}) \\ = & 21 \cdot 2^{n - 1} + 49 \cdot 5^{n - 1} - 30 \cdot 2^{n - 2} - 70 \cdot 5^{n - 2}) \\ = & 21 \cdot 2^{n - 1} + 49 \cdot 5^{n - 1} - 15 \cdot 2^{n - 1} - 14 \cdot 5^{n - 1}) \\ = & 6 \cdot 2^{n - 1} + 35 \cdot 5^{n - 1} \\ = & 3 \cdot 2^{n} + 7 \cdot 5^{n} = a_{n} \end{aligned}$

. So the closed formula agrees with the recurrence relation. The closed formula has initial terms $a sub 0 equals 10$ and $a sub 1 equals 41$ .

Show that $a_{n} = 2^{n} - 5^{n}$ is also a solution to the recurrence relation $a_{n} = 7 a_{n - 1} - 10 a_{n - 2}$ . What would the initial conditions need to be for this to be the closed formula for the sequence?

Find a closed formula for the sequence with recursive definition $a_{n} = 2 a_{n - 1} - a_{n - 2}$ with $a sub 1 equals 1$ and $a sub 2 equals 2$ .

You will want to write out the sequence, guess a closed formula, and then verify that you are correct.

Give two different recursive definitions for the sequence with closed formula $a_{n} = 3 + 2 n$ . Prove you are correct. At least one of the recursive definitions should makes use of two previous terms and no constants.

Write out the sequence, guess a recursive definition, and verify that the closed formula is a solution to that recursive definition.

Use summation ( $∑$ ) or product ( $∏$ ) notation to rewrite the following.

$2 + 4 + 6 + 8 + \dots + 2 n$ .
$1 + 5 + 9 + 13 + \dots + 425$ .
$1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{50}$ .
$2 \cdot 4 \cdot 6 \cdot \dots \cdot 2 n$ .
$(\frac{1}{2}) (\frac{2}{3}) (\frac{3}{4}) \dots (\frac{100}{101})$ .

$∑ k equals 1 n 2 k$ .
$\sum_{k = 1}^{107} (1 + 4 (k - 1))$ .
$\sum_{k = 1}^{50} \frac{1}{k}$ .
$∏ k equals 1 n 2 k$ .
$\prod_{k = 1}^{100} \frac{k}{k + 1}$ .

Expand the following sums and products. That is, write them out the long way.

$\sum_{k = 1}^{100} (3 + 4 k)$ .
$\sum_{k = 0}^{n} 2^{k}$ .
$\sum_{k = 2}^{50} \frac{1}{(k^{2} - 1)}$ .
$\prod_{k = 2}^{100} \frac{k^{2}}{(k^{2} - 1)}$ .
$\prod_{k = 0}^{n} (2 + 3 k)$ .

$\sum_{k = 1}^{100} (3 + 4 k) = 7 + 11 + 15 + \dots + 403$ .
$\sum_{k = 0}^{n} 2^{k} = 1 + 2 + 4 + 8 + \dots + 2^{n}$ .
$\sum_{k = 2}^{50} \frac{1}{(k^{2} - 1)} = 1 + \frac{1}{3} + \frac{1}{8} + \frac{1}{15} + \dots + \frac{1}{2499}$ .
$\prod_{k = 2}^{100} \frac{k^{2}}{(k^{2} - 1)} = \frac{4}{3} \cdot \frac{9}{8} \cdot \frac{16}{15} \dots \frac{10000}{9999}$ .
$\prod_{k = 0}^{n} (2 + 3 k) = (2) (5) (8) (11) (14) \dots (2 + 3 n)$ .

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}$ . Find a recursive formula for the number of regions created by $n$ lines, and justify why your recursion is correct.

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.

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$ . For example, $G sub 1 equals 3$ , and $G sub 2 equals 8$ (since of the 9 ternary strings of length 2, only one is not good).

Find, with justification, a recursive formula for $G_{n}$ , and use it to compute $G sub 5$ .

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.

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$ . 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$ .

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 equals 1$ ? How many have sum $n equals 2$ ? And so on. Find and explain a recurrence relation for the sequence $(a_{n})$ which gives the number of strings with sum $n$ .
Describe what you have found above in terms of Pascal's Triangle. What pattern have you discovered?

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

A honeycomb of twelve hexagons arranged as two staggered rows of six, forming a horizontal strip. The leftmost hexagon of the upper row is labeled start and the rightmost hexagon of the lower row is labeled stop. The second hexagon of the lower row is labeled 3. Each hexagon shares an edge with the hexagons to its right, upper right, and lower right.

Think recursively, like you did in Pascal's triangle.

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 $open parenthesis t sub n close parenthesis sub n greater than or equal to 1$ and then give a recursive definition. Explain why your recursive formula is correct.

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.

Discrete Mathematics: An Open Introduction, 3rd edition, by Oscar Levin (discrete.openmathbooks.org), licensed under CC BY-SA 4.0; this adaptation is distributed under the same license. License: CC-BY-SA-4.0.