Sequence
A sequence is an ordered list of terms. Sequences can be finite or infinite. Sequences can be listed or defined in a variety of ways. Here are some sequences: \[1,1,1,1,1,...\] \[2,4,6,8,10\] \[1,1,2,3,5,8,...\] \[0, 0.01, 0.0011, 0.000111, 0.00001111, ... \] \[\frac{0}{1},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{1}{1}\] The ellipses (...) indicate that the sequence continues.
Formulating Sequences
An explicit formula is one that calculates the \(n^{\text{th}}\) term of a sequence directly. The \(n^{\text{th}}\) perfect square is given by \[a_n = n^2 \] for \(n \geq 1\). The subscript is an index which refers to a particular term in a sequence. It is common to start with subscripts of either 0 or 1. The sequence defined by the formula above is \(a_1, a_2, a_3, ...\), where: \[a_1 = 1\] \[a_2 = 4\] \[a_3 = 9\] \[...\]
A recursive definition consists of an initial condition and recurrence relation for calculating each term from previous terms. Consider: \[a_1 = \frac{1}{2}\] \[a_n = 3a_{n-1}\] This says that every term is equal to \(3\) times the previous term, with the first term being \(\frac{1}{2}\). This definition gives us the sequence: \[a_{1} = \frac{1}{2}\] \[a_{2} = \frac{3}{2}\] \[a_{3} = \frac{9}{2}\] \[a_{4} = \frac{27}{2}\]
Exercise
Find \(a_6\) in the sequence defined by \(a_n = 2a_{n-1}-a_{n-2}\) with \(a_0 = 3\) and \(a_1=4\).
To find \(a_6\) we would need: \[ a_6 = 2a_5 - a_4 \] but we do not know \(a_5\) or \(a_4\) yet. The typical strategy for evaluating terms recursivly is to start at the beginning and work up to our target term.
We are given: \[a_0 = 3\] \[a_1 = 4\] and we continue with: \[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 \]
Below are examples of sequences with their explicit and recursive formulas.
| Sequence | Explicit | Recurisve |
|---|---|---|
| \(1,2,3,4,5, ...\) | \[a_n = n\] \[n \geq 1 \] | \[a_0 = 1\] \[a_n = a_{n-1}+1\] |
| \(0,2,4,6,8 ...\) | \[a_n = 2n\] \[n \geq 0 \] | \[a_0 = 0\] \[a_n = a_{n-1}+2\] |
| \(1,2,4,8,16, ...\) | \[a_n = 2^n\] \[n \geq 0 \] | \[a_0 = 1\] \[a_n = 2a_{n-1}\] |
| \[\frac{1}{3},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{5}{7},... \] | \[a_n = \frac{n}{n+2}\] \[n \geq 1 \] | I don't know |
| \[ 1,1,1,3,5,9,17,... \] | I don't know | \[a_0 = 1, a_1 = 1, a_2 = 1\] \[a_n = a_{n-1}+a_{n-2}+a_{n-3}\] |
Exercise
Find both a explicit and recursive definition for the sequence: \[ 5, 8, 11, 14, ... \]
Observe that the first term is \(5\) and there is a common difference of \(3\).
We can write a recursive definition by stating the initial condition and recurrance relation: \[a_0 = 5\] \[a_n = a_{n-1}+3\]
We can write an explicit formula as: \[ a_n = 5 + 3n \] Notice that when \(n=0\) we have \(5+3(0)\). It is always good to verify your formula!
Some famous sequences include:
| \(1,4,9,16,25, ...\) | The square numbers. The sequence \((s_n)_{n \geq 1}\) has closed formula \(s_n = n^2\) |
| \(1,3,6,10,15,21, ...\) | The triangular numbers. The sequence \((T_n)_{n \geq 1}\) has closed formula \(T_n = \frac{n(n+1)}{2} \) |
| \(1,2,4,8,16,32, ...\) | The powers of 2. The sequence \((a_n)_{n \geq 0}\) has closed formula \(a_n = 2^n\) |
| \(1,1,2,3,5,8,13, ...\) | The Fibonacci numbers are defined recursively by \(F_1=F_2=1\), \(F_{n} = F_{n-1}+F_{n-2}\) |
Exercise
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\).
- \( (b_n): 1,2,4,7,11,16,22,... \)
- \( (c_n): 3,5,9,17,33,... \)
- \( (d_n): 0,2,6,12,20,30,42,... \)
- \( (e_n): 3,6,10,15,21,28,... \)
- \( (f_n): 0,1,3,7,15,31,... \)
- \( (g_n): 3,6,12,24,48,... \)
- \( (h_n):6,10,18,34,66,... \)
- \( (j_n): 15, 33, 57, 87, 123, ... \)
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 we 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 what 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{.}\)
Sequence Behavior
For an infinite sequence, a natural question regards the behavior of \(a_n\) as \(n\) goes to infinty. There are some common behaviors we want to be able to recognize and analyize.
Some sequences will just get bigger, tending toward \(\pm \infty\), for example: \[1,2,3,4,5,...\] \[2,4,6,8,10,...\] \[-2, -3, -5, -7, -11, -13, ...\] \[\sqrt{1}, \sqrt{2}, \sqrt{3}, \sqrt{4}, ...\]
Other sequences converge to a single number. Cosider these sequences: \[ \frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\frac{1}{6}, ... \] \[1, 0.1, 0.001, 0.0001, 0.00001, ...\] \[ \frac{1}{1}, \frac{2}{2^2}, \frac{3}{3^2}, \frac{4}{4^2} \] For all of these sequences, \(a_n \to 0\) as \(n \to \infty\), or using limit notation: \[ \lim_{n \to \infty} a_n = 0 \]
Other sequences cycle. The sequence given by: \[a_0 = 3 \quad \quad a_n = -1 a_{n-1}\] is the alternating sequence: \[3, -3, 3, -3, 3, ...\] We would call this a \(2\)-cycle since it cycles between two values.
Other sequences do not cycle, converge, or go off to infinity. The sequence of digits in \(\pi\) are values from \(0\) to \(9\) that do not converge and do not cycle.
Sum
We will find several applications that involve summing a sequence. Even infinite sequences! Given the infinite sequence: \[ \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, ... \] The corresponding sum is: \[ \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + ... \] which amazingly is an infinite sum equal to \(1\). A formula for this sequence of reciprocal powers of \(2\) is: \[ a_n = \frac{1}{2^n} \quad \quad n \geq 1 \] which we can use to write the sum using sigma notation. That summation looks like: \[ \sum_{n=1}^{\infty} a_n = \sum_{n=1}^{\infty} \frac{1}{2^n} \] where the subscript \(n=1\) represents the starting value of \(n\) and the superscript represents the final value.
We can also write sums of finite sequences or partial sums of infinite sequences. The sum of the first five perfect squares is: \[\sum_{i=1}^{5} x^2 = (1)^2 + (2)^2 + (3)^2 + (4)^2 + (5)^2\]
Exercise
Use \(\sum\) notation to rewrite the sums:
- \( \quad 1 + 2 + 3 + 4 + \dots + 100 \)
- \( \quad 1 + 2 + 4 + 8 + \dots + 2^{50} \)
- \( \quad 6 + 10 + 14 + \dots + (4n-2) \)
- \[ \sum_{k=1}^{100} k \]
- \[ \sum_{k=0}^{50} 2^k \]
- \[ \sum_{k=2}^{n} (4k-2) \]