Sequence is a bunch of any entities (objects) arranged in a specific order. Any elements (entities) can create a sequence. It can be numbers, alphabets, even formulas.. but one condition is that there should be a certain rules between an elements and previous elements). Simply put we should be able to find a certain rules to create a given sequence.

On this page I'll start with the notation. Then I'll look at rules that build an element from earlier ones, and at the engineering case where one sequence is built from another. Five worked examples follow. The last section asks where a sequence goes as n grows.

• How is a sequence written in mathematical form ?
• How is an element built from the previous elements ?
• How is a sequence built from another sequence ?
• How do you find the rule of a given sequence ? - Examples
• Does a sequence settle to a value ? - Convergence

How is a sequence written in mathematical form ?

If I represents a sequence in an illustration, it can be as shown below. This illustration shows many triangles arranged in a certain pattern. So we can call it as "a sequence of triangles in pattern X" (Let's think about the 'pattern X' later).

Important things about the sequnce in practice is to understand and get familiar with mathematical representation of the sequence. There are several different ways of mathematical representation of the sequence. It is important for you to get familiar with all the different types of representation.

One of the most common way of representing a sequence in a mathematical form is the one as labeled 'Mathematical representation - I'. It assigned a letter 'a' as indicating elements of the sequence and uses subcriptions (I call this as an 'index') to indicator the specific position of the element 'a' within the sequence. Notice that the index starts from '0', not '1'. Starting from index 0 is not a mandatory. you can label it from index 1 if you like, but it is more common to use index 0 as the starting element.

Another form of mathematical representation would be as labeled as 'Mathematical representation - II'. It is much more compact than the 'Mathematical representation - I', but it may look more intimidating (scary) if you are not familiar with this area.

• Intuitive representation : the top row draws the elements themselves, six triangles and then dots for the elements that follow.
• Mathematical representation - I : each element gets the name a with its position as a subscript, a₀, a₁, a₂ and so on. The symbol a_k on the left stands for the whole list.
• Mathematical representation - II : (a_n)_n=0^k-1 packs the same list into one symbol. n is the index, and it runs from 0 to k-1.
• k is the number of elements : the label in the picture points at k-1, but k-1 is the last index. The index starts at 0, so a sequence with indices 0 to k-1 has k elements. For an infinite sequence the upper limit is written as ∞.

Keep one practical point from this section. When a book writes a sequence as (a_n), check where its index starts before you compare elements. Depending on that choice, a₁ is the first or the second element.

• A sequence is an ordered list : the index gives the position, and changing the order gives a different sequence.
• The index usually starts at 0 on this page : starting at 1 is also correct, as long as you use one choice consistently.
• Both notations describe the same list : a₀, a₁, ... shows the elements, and (a_n) is the compact form.

How is an element built from the previous elements ?

The two forms mathematical representation shown above would show the 'order' of the elements within the sequence, but it does not show the relationships between an element and another element. To show this relation between elements sometimes we represents a sequence as follows. This examples shows 'within the sequence 'a', an elements can be generated from the previous element and a 'rule'.

• a_n is the current element : this is the value to be found.
• a_n-1 is the previous element : the rule is applied to it. The picture writes the rule as a product, a_n-1 x rule. But the rule can be any operation, which is why the second line writes it as a function, f(a_n-1).
• The first element has to be given : a₀ has no previous element, so the rule cannot produce it.

What do you see in terms of pattern in the triangle sequence you saw at the beginning ? Are they arrange in a random pattern ?

Let me give you the answer since I am the one who created the sequence -:)

a(0) = first triangle = this should be given by the person who created/defined the sequence since there is no previous element. We cannot apply any 'rule' to create the first triangle in the example.

a(1) = second triangle = expand the first triangle a little bit and rotate it to the right a little bit.

a(2) = third triangle = expand the second triangle a little bit and rotate it to the right a little bit.

a(3) = fourth triangle = expand the third triangle a little bit and rotate it to the right a little bit.

a(4) = fifth triangle = expand the fourth triangle a little bit and rotate it to the right a little bit.

Now can you see any pattern and describe the triangle sequence in a mathematical form ? I can be represented as follows.

a(n) = 'expand and rotate a(n-1)', where n > 0

It means that any element (except the first element) can be created by 'expanding and rotating a previous element.

In this example, we saw a case where an element is created by apply a rule to only 'IMMEDIATE PREVIOUS' element, but this is not the only case.

There can be some case as follows

• An element is created by a rule and previous and previous-previous elements.
• An element is created by a rule and previous and previous-previous and previous-previous-previous elements.
• An element is created by a rule and previous and previous-previous, previous-previous-previous and previous-previous-previous-previous elements.
• .....

If we represent this kind of sequence generation in a more formal form (fancy but scary -:)), it would look as follows. f() in the form represents a rule. Just don't get scared.. just don't run away and take closer look at the mathematical form and describe it in plain language as I did above.

• f is the rule : it takes the previous elements and returns the current one.
• a_n-1 to a_n-m are the m previous elements : m is called the order of the recursion. The Fibonacci sequence in Example 3 uses m = 2.
• r is the offset : a constant that does not depend on any element, such as the +1 in Example 1.
• m elements must be given at the start : the rule needs m previous values, so a₀ to a_m-1 are set by hand. These are the initial conditions.

I just described a couple of most common form of mathematical representation for a sequence. There would be other variations. Whenever you see a sequence in a mathmatical form, try to create several elements of the sequence on your own until you get the clear understanding of the mathematical representation.

Please refer to the following link (if you want to get some high school class style explanation) : Math is Fun - Sequence (I think this is excellent explanation)

So far we have seen two kinds of rules. An explicit rule computes an element from its index alone, such as a_n = 2n. A recursive rule computes it from earlier elements, such as a_n = a_n-1 + 2. The explicit form lets you jump straight to a₁₀₀₀. The recursive form often matches how a system works step by step, and it is the form that a computer loop uses. Examples 1 to 3 below show both forms for the same sequence.

• A recursive rule needs initial values : the number of given elements equals the number of previous elements that the rule uses.
• One sequence can have several rules : a_n = n and a_n = a_n-1 + 1 with a₀ = 0 give the same list.
• Check a rule by generating elements : compute the first few elements from the rule and compare them with the given list.

How is a sequence built from another sequence ?

The sequence I metioned above is something that you might see often in your math class. In case of engineering course, you may more often see the sequence as follows. All most all the engineering area dealing with discrete data (e.g, digital data) would use this kind of sequence. So you'd better be very familiar with logic behind these and mathematical representation introduced here.

In this case, a sequence (labeled as y(n) is created from another sequence (labeled as x(n)) by applying a certain rule.

Let's assume we are given a sequence generation rule as shown below

You can generate each elements of the current sequence (y(n)) just by plugging in elements of the other sequence (x(n)) according to the rule as shown below.

Let's put numbers in. Take x = {2, 4, 6, 8, ...}. The rule gives y₁ = (2 + 4)/2 = 3, y₂ = (4 + 6)/2 = 5 and y₃ = (6 + 8)/2 = 7. Each y is the average of the current and the previous x, so this rule is a two-point moving average. The first output y₀ has to be given, because x_-1 does not exist.

Now let's look into another example sequence which is generated from combination of the other sequence (x(n)) and the current sequence (y(n)).

Let's assume that we are given the sequence generation rule as shown below. Notice that the rule here contains not only 'the other sequence (x(n))' but also the current sequence (y(n)).

Just plugging in appropriate elements of the sequence x and y, you can generate each of the elements of sequence y as shown below.

With the same x = {2, 4, 6, 8, ...} and y₀ = 1, this rule gives y₁ = (2 + 4)/1 = 6. Then y₂ = (4 + 6)/6 = 1.667 and y₃ = (6 + 8)/1.667 = 8.4. Now each output depends on the previous output as well, so an early value keeps affecting everything after it. Note also that this particular rule divides by y_n-1. That makes it nonlinear, and it fails as soon as one y becomes 0.

You can represent a general rule to create a sequence y based on both the sequence x and sequence y as shown below. Just don't get panic and skip this part. Just try to think of each component of the expression and describe it in plain language.

• x_n-1 to x_n-m : previous elements of the other sequence, which is often called the input.
• y_n-1 to y_n-m : previous elements of the current sequence, which is often called the output. Using them is called feedback.
• x_offset and y_offset : constant terms that do not depend on n.
• The current input x_n is missing from the picture : both rules above use x_n, so a complete general form has x_n as the first argument of f.

In signal processing this kind of rule is called a difference equation, and it is how a digital filter is written. The most common case is linear, y_n = b₀x_n + b₁x_n-1 + ... + b_Mx_n-M - a₁y_n-1 - ... - a_Ny_n-N. When all the a coefficients are 0, the output depends only on the input. That is an FIR filter, and the moving average above is one. When some a coefficient is not 0, the output feeds back into the rule. That is an IIR filter.

• Input and output are both sequences : a rule turns the input sequence x into the output sequence y one element at a time.
• Feedback needs initial values of y : without y₀ the first output cannot be computed.
• A linear rule is a digital filter : an FIR filter uses only x, and an IIR filter also uses earlier y.

How do you find the rule of a given sequence ? - Examples

Now let's look into several examples to get you more familiar with the concept or mathematical representation of a sequence. In each one, try to find the rule yourself before reading the answer. Look first at how each element relates to its index, and then at how it relates to the elements before it.

Example 1

The first example is the simplest sequence there is, the counting numbers. It is simple on purpose, so that we can concentrate on writing the rule down in both forms.

Find the mathematical rule for the following sequence.

I know you intuitively grasp the meaning of this sequence.. but may have some difficulties in representing in a mathematical form.

If you look into the sequence more closely, you would notice that the value of each element is same as the index of the element. So this sequence can be represented as shown below.

How do you know if this is correct mathematical representation of the sequence ?  It is simple. Just try to create each elements of the sequence from this rule.

Can you find another rule showing the relationship between an element (or multiple elements) and another element ?

It will come out as follows. Can you make sense out of this equation ? It says "An element of the sequence can created by taking a 'previous element + 1'.

Example 2

The second example changes the step from 1 to 2. Compare the two rules with those of Example 1 and notice which part of each rule changes.

Find the mathematical rule for the following sequence.

I know you intuitively grasp the meaning of this sequence.. but may have some difficulties in representing in a mathematical form.

If you look into the sequence more closely, you would notice that the value of each element is twice the index of the element. So this sequence can be represented as shown below.

How do you know if this is correct mathematical representation of the sequence ?  It is simple. Just try to create each elements of the sequence from this rule.

Can you find another rule showing the relationship between an element (or multiple elements) and another element ?

It will come out as follows. Can you make sense out of this equation ? It says "An element of the sequence can created by taking a 'previous element + 2'.

Note that this recursive rule also needs a starting value, a₀ = 0, even though the picture does not write it. Without it, a_n = a_n-1 + 2 describes every list that steps by 2, such as 1, 3, 5, 7, ...

Example 3

The third example is harder. Neither the index nor a fixed step between elements explains it, so you will need to look at more than one previous element.

Find the mathematical rule for the following sequence.

Unlike previous two examples, I don't think you come out with any pattern in such an easy way. Can you find any answer to the following questions ?

Don't get disappointed if you failed to find a rule for this. I am pretty sure that I would not find the rule if I haven't r recalled a special pattern called 'Fibonacci sequence' that I learned in high school math. Definately this is not what I found, it is just what Fibonacci found.

Anyway the answer is as follows. It says an elements in the sequence can be created by taking "previous-previous element + previous element'. Since it requires two previous elements, the first two elements should be given as shown below. Depending on which value is given to the first two elements, the value for all the next elements will get different.

The question in the middle of this example also has an answer. The Fibonacci sequence has an explicit rule, called Binet's formula, a_n = (φⁿ - ψⁿ)/√5. Here φ = (1 + √5)/2 = 1.618 and ψ = (1 - √5)/2 = -0.618. The formula gives a whole number for every n, for example a₁₀ = 55. The explicit rule is far from obvious, and this is typical. A recursive rule is often easy to see, while the explicit one needs real work.

The ratio of neighboring elements also approaches φ. For example, 21/13 = 1.615, 34/21 = 1.619 and 89/55 = 1.618. The last section of this page comes back to this ratio.

Example 4

Now let's look into another example. Now I will give you just a rule for creating a sequence. Even though it would be a little daunting (scary) since it is a mathematical form, it would be much easier to generate the sequence if the rule is given.

As you are already familiar, 'n' in this rule indicate 'index' (location of the element in the sequence).  This rule says "If you only know the index of an element, you can generate the value for the element just by plugging the index into the rule as shown below.

With these calculated values, you can come out with a sequence as shown below. Isn't it simple ?

You can read two things from this list. The sign alternates because of the factor (-1)ⁿ⁺¹, and the size grows because of the factor 2n. Note that a₀ = 0, so the list starts with 0 and the first negative element is a₂ = -4.

Example 5

The last example is the engineering case from the section on building a sequence from another one. A noisy input sequence x goes through a rule, and the output sequence y is a cleaner version of it.

Let's assume we have the following sequence.

Assume that the sequence y is created by another sequence x according to following rule.

This rule is the average of the current element and the three previous ones, so it is a four-point moving average. It needs x_n-3, which only exists from n = 3 on. That is why y₀, y₁ and y₂ are given as 0.

Assume that the sequence x has elements as shown below.

The sequence generated by the given rule should be as shown below. (For the generation of each elements of the sequence y, look into this spreadsheet)

• The input x is a sine wave plus noise : in the spreadsheet, x(n) = SIN(0.1n) + 0.3*RAND() for n = 0 to 82. RAND() is uniform between 0 and 1, so the noise lies between 0 and 0.3. The spreadsheet draws new noise every time it recalculates.
• The output y is smoother : averaging four samples reduces the random part. For independent noise the standard deviation falls by √4 = 2, from 0.087 to 0.043. The values saved in the spreadsheet give 0.084 and 0.041.
• The sine wave passes almost unchanged : one period is 2π/0.1 = 63 samples, far longer than the 4-sample window. Its amplitude is scaled by only 0.994.
• The output lags by 1.5 samples : the average is centered between x_n-3 and x_n.
• The first three y are 0 : these are the given initial values, and they show as the flat start of the y plot.
• The noise mean is not removed : RAND() adds 0.15 on average, and averaging keeps it. So both plots sit about 0.15 above a pure sine.

Does a sequence settle to a value ? - Convergence

Once a sequence is written down, the next question is where it goes as n grows. Some sequences settle closer and closer to one number. Others grow without limit or keep jumping around. This matters because a series is built from a sequence, and many numerical methods produce a sequence that has to settle.

A sequence converges to a limit L when its elements get as close to L as you like and stay there. Formally, for every small tolerance ε > 0 there is an index N such that |a_n - L| < ε for every n > N. The idea is the same as the limit of a function on the Limit page, with n in place of x. A sequence that has no limit diverges. The table below sorts some sequences from this page and a few new ones.

A recursive rule can also converge, and many algorithms find a number this way. The rule a_n = (a_n-1 + 2/a_n-1)/2 with a₀ = 1 gives 1, 1.5, 1.41667, 1.414216 and 1.4142136. The elements settle on √2 = 1.4142136, and the number of correct digits roughly doubles at every step. This rule is Newton's method applied to x² = 2.

• Convergence depends only on large n : the first elements do not matter, only where the elements go as n grows.
• Growing and alternating are two ways to diverge : Example 2 grows, and (-1)ⁿ never settles even though it stays between -1 and 1.
• A finite series needs elements that go to 0 : this condition is necessary but not enough, as the harmonic series on the Series page shows.