Describing Sequences

Section Preview

Investigation

There is a monastery in Hanoi, as the legend goes, with a great hall containing three tall pillars. Resting on the first pillar were 64 giant disks (or washers), all different sizes, stacked from largest to smallest. The monks of the monastery have been moving the disks for generations, attempting to move the entire stack of disks to the third pillar. However, due to the size of the disks, the monks cannot move more than one at a time. Each disk must be placed on one of the pillars before the next disk is moved. And because the disks are so heavy and fragile, the monks may never place a larger disk on top of a smaller disk. When the monks finally complete their task, the world shall come to an end.

Your task: Figure out how long it will be before we need to start worrying about the end of the world.

This puzzle is called the Tower of Hanoi. You are tasked with finding the minimum number of moves to complete the puzzle. This certainly sounds like a counting problem. Perhaps you have an answer? If not, what else could we try?

The answer to the puzzle depends on the number of disks you need to move. In fact, we could answer the puzzle first for 1 disk, then 2, then 3, and so on. If we list all of the answers for each number of disks, we will get a sequence of numbers. The \(n\)th term in the sequence is the answer to the question, What is the smallest number of moves required to complete the Tower of Hanoi puzzle with \(n\) disks?

Give it a try. Find the smallest number of moves needed to transport the stack of \(n\) disks to another pillar, for different values of \(n\).

You might wonder why we would create such a sequence instead of just answering the question. By looking at how the sequence of numbers grows, we gain insight into the problem. It is easy to count the number of moves required for a small number of disks. We can then look for a pattern among the first few terms of the sequence. Hopefully this will suggest a method for finding the \(n\)th term of the sequence, which is the answer to our question. Of course we will also need to verify that our suspected pattern is correct, and that this correct pattern really does give us the \(n\)th term that we think it does, but it is impossible to prove that your formula is correct without having a formula to start with.

In this section, we will explore how to represent sequences of numbers in various ways, and two sorts of formulas that can be used to describe the sequence. We will see that sequences are also interesting mathematical objects to study in their own right.

Sequences and Formulas

A sequence is simply an ordered list of numbers. Unlike a set of numbers, the order of the numbers in a sequence is an essential characteristic of the sequence. For this reason, when we use variables to represent terms in a sequence they will look like this: \[a_0, a_1, a_2, a_3, \ldots\]. To refer to the entire sequence at once, we will write \((a_n)_{n\in\N}\) or \((a_n)_{n\ge 0}\), or sometimes if we are being sloppy, just \((a_n)\) (in which case we assume we start the sequence with \(a_0\)). \((a_n)_{n \in \N}\) the sequence \(a_0, a_1, a_2, \ldots\)

We might replace the \(a\) with another letter, and sometimes we omit \(a_0\), starting with \(a_1\), 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\). 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

Can you find the next term in the following sequences?

1. \(7,7,7,7,7, \ldots\)
2. \(3, -3, 3, -3, 3, \ldots\)
3. \(1, 5, 2, 10, 3, 15, \ldots\)
4. \(1, 2, 4, 8, 16, 32, \ldots\)
5. \(1, 4, 9, 16, 25, 36, \ldots\)
6. \(1, 2, 3, 5, 8, 13, 21, \ldots\)
7. \(1, 3, 6, 10, 15, 21, \ldots\)
8. \(2, 3, 5, 7, 11, 13, \ldots\)
9. \(3, 2, 1, 0, -1, \ldots\)
10. \(1, 1, 2, 6, \ldots\)

Solution

No, you cannot.

You might guess that the next terms are:

1. \(7\)
2. \(-3\)
3. \(4\)

4. 64

5. 49

6. 34

7. 28

8. 17

9. \(-2\)
10. \(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.

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

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Partial Sums and Differences

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

Example

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 \[3, 5, 6, 10, 9, 0, 12, \ldots\]. Describe a sequence \((b_n)_{n \ge 1}\) that gives 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. \[3, 8, 14, 24, 33, 33, 45,\ldots\]. Here \(b_1\) is just \(a_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-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 + \cdots + 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 \((a_n)_{n \in \N}\), we can always form a new sequence \((b_n)_{n \in \N}\) by \[b_n = a_0 + a_1 + a_2 + \cdots + a_n\]. Since the terms of \((b_n)\) are the sums of the initial part of the sequence \((a_n)\), we 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 \(\d\sum_{k=1}^n a_k\). This means add up the \(a_k\)'s where \(k\) changes from 1 to \(n\).

Example

Use \(\sum\) notation to rewrite the sums:

1. \(1 + 2 + 3 + 4 + \cdots + 100\)
2. \(1 + 2 + 4 + 8 + \cdots + 2^{50}\)
3. \(6 + 10 + 14 + \cdots + (4n - 2)\)

Solution

1. \(\d\sum_{k=1}^{100} k\)
2. \(\d\sum_{k=0}^{50} 2^k\)
3. \(\d\sum_{k=2}^{n} (4k -2)\)

In general, it is easy to go from a closed formula for a sequence to a closed formula for the sequence of differences. It is not always easy to go the other way around. In fact, what would it look like to start with a sequence of differences and get the original sequence?

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Sequences in python

Checking that a closed formula agrees with the initial terms in a sequence is easy with a calculator, or better yet, a programming language like python. One way you can do this is to define a function that returns the \(n\)th term of the sequence.

Here is an example: Suppose you wanted to check whether a formula you found for the sequence \((a_n)_{n \in \N} = (1, 3, 7, 15, 31,\ldots)\) is correct. Perhaps you guess that \(a_n = 2^n-1\). Try running the code below. (Note: In python, the ^ symbol means something else, so to do exponentiation, we use **.)

Looks promising, but we should be careful: Our sequence started with \(a_0 = 1\), which makes \(a_3 = 15\). Now try modifying the definition of a(n) (by changing the return value) to get the correct closed formula.

Perhaps you want to print out the first 20 terms of the sequence? This is easy to do with python, by putting the terms in a list:

Note that range(20) starts at 0 and stops at 19 (it is the list [0,1,2,...,19]).

We can also use python to generate terms for a sequence given a recursive definition. Suppose we wanted to explore the sequence \(a_n = 2a_{n-1}+1\) with initial condition \(a_0 = 1\). In python, we could generate the sequence as follows.

Do you see how to translate a recurrence relation into a recursive python function? Try playing around with the code above to explore other sequences.

Practice (19)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. For the formulas for sequences below, select all that are closed formulas (as opposed to recursive formulas).

2. Drag each sequence on the left to a recurrence relation that agrees with the sequence.

3. What questions do you have? Write at least one question about the content of this section that you or a classmate might be curious about after reading this section.

4. Consider the sequence \((a_n)_{n \ge 1}\) that starts \(1, 3, 5, 7, 9, \ldots\) (i.e., the odd numbers in order).

   1. Give a recursive definition and closed formula for the sequence.

   2. Write out the sequence \((b_n)_{n \ge 2}\) of partial sums of \((a_n)\). Write down the recursive definition for \((b_n)\) and guess at the closed formula.

   Paljasta vastaus

   1. The recursive definition is \(a_n = a_{n-1} + 2\) with \(a_1 = 1\). A closed formula is \(a_n = 2n-1\).

   2. The sequence of partial sums is \(1, 4, 9, 16, 25, 36, \ldots\). 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\). It appears that the closed formula is \(b_n = n^2\)

5. \(F_n\) the \(n\)th Fibonacci number

   The Fibonacci sequence is \(0, 1, 1, 2, 3, 5, 8, 13, \ldots\) (where \(F_0 = 0\)).

   1. Write out the first few terms of the sequence of partial sums: \(0\), \(0+1\), \(0+1+1\),

   2. 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\), although that is definitely not correct.

   Paljasta vastaus

   1. \(0, 1, 2, 4, 7, 12, 20, \ldots\)
   2. \(F_0 + F_1 + \cdots + F_n = F_{n+2} - 1\)

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

   1. \(2, 4, 6, 10, 16, 26, 42, \ldots\)
   2. \(5, 6, 11, 17, 28, 45, 73, \ldots\)
   3. \(0, 0 , 0 , 0 , 0 , 0 , 0 ,\ldots\)

   Paljasta vastaus

   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.

7. Write out the first few terms of the sequence given by \(a_1 = 3\); \(a_n = 2a_{n-1} + 4\). Then find a recursive definition for the sequence \(10, 24, 52, 108, \ldots\).

   Paljasta vastaus

   \(3, 10, 24, 52, 108,\ldots\). The recursive definition for \(10, 24, 52, \ldots\) is \(a_n = 2a_{n-1} + 4\) with \(a_1 = 10\).

8. Write out the first few terms of the sequence given by \(a_n = n^2 - 3n + 1\). Then find a closed formula for the sequence (starting with \(a_1\)) \(0, 2, 6, 12, 20, \ldots\).

   Paljasta vastaus

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

9. 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}\). What would the initial conditions need to be for this to be the closed formula for the sequence?

   Paljasta vastaus

   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}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\end{aligned}\]. So the closed formula agrees with the recurrence relation. The closed formula has initial terms \(a_0 = 10\) and \(a_1 = 41\).

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

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

    Paljasta vastaus

    Hint:

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

12. Give two different recursive definitions for the sequence with closed formula \(a_n = 3 + 2n\). Prove you are correct. At least one of the recursive definitions should make use of two previous terms and no constants.

    Paljasta vastaus

    Hint:

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

13. Use summation (\(\sum\)) or product (\(\prod\)) notation to rewrite the following.

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

    Paljasta vastaus

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

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

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

    Paljasta vastaus

    1. \(\d\sum_{k=1}^{100} (3+4k) = 7 + 11 + 15 + \cdots + 403\)
    2. \(\d\sum_{k=0}^n 2^k = 1 + 2 + 4 + 8 + \cdots + 2^n\)
    3. \(\d\sum_{k=2}^{50}\frac{1}{(k^2 - 1)} = 1 + \frac{1}{3} + \frac{1}{8} + \frac{1}{15} + \cdots + \frac{1}{2499}\)
    4. \(\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}\)
    5. \(\d\prod_{k=0}^n (2+3k) = (2)(5)(8)(11)(14)\cdots(2+3n)\)

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

    Paljasta vastaus

    Hint:

    Try an example: When you draw the 4th line, it will cross three other lines and so will be divided into four segments, two of which are infinite. Each segment will divide a previous region into two.

16. 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_1 = 3\), 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\), and use it to compute \(G_5\).

    Paljasta vastaus

    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 they require a little more work.

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

    1. Find examples of these strings of different lengths. What is the longest string possible? What is the shortest?

    2. How many strings are there of each of these lengths. Use this to count the total number of strings (with sum 11).

    3. The other approach: Let \(n = l+k\) vary. How many strings have sum \(n = 1\)? How many have sum \(n = 2\)? And so on. Find and explain a recurrence relation for the sequence \((a_n)\) that gives the number of strings with sum \(n\).

    4. Describe what you have found above in terms of Pascal's triangle. What pattern have you discovered?

18. 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 how this relates to the previous question. (As an example, there are three paths to get to the second hexagon on the bottom row.)

    Paljasta vastaus

    Hint:

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

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

    Paljasta vastaus

    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.

Symbols used here

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

i

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

n!

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

A \cup B,\ A \cap B,\ A \setminus B

union, intersection, difference
In either; in both; in A but not B.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

\forall,\ \exists

for all, there exists
Quantifiers: every x; at least one x.

\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow

not, and, or, implies, iff
Logical connectives.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

O(n^2),\ \Theta,\ \Omega

big-O notation
Grows no faster than n² (up to a constant), for large n.

a \bmod n

remainder
What is left after dividing a by n.

How to: Describing Sequences

1. Use proper notation to represent a sequence.
2. Explain the difference between a closed formula and a recursive definition for a sequence.
3. Find a recursive definition for a sequence based on its description.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Kokeile omaasi

⌨ Type ✎ Draw

Matematiikkaongelmasi

Ratkaise

x²√÷×π( )=∫d/dxlim[ ]sinlogeˣ

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Lisää Discrete Math & Logic

Truth tablesSums and inductionProof by inductionAlgorithms and growth of functions