Return to the Purplemath home page

 The Purplemath Forums
Helping students gain understanding
and self-confidence in algebra


powered by FreeFind

 

Return to the Lessons Index  | Do the Lessons in Order  |  Get "Purplemath on CD" for offline use  |  Print-friendly page



Finding the Next Number in a Sequence:
     Recursive Sequences
(page 3 of 7)

Sections: Common differences, Recursions, General examples, Non-math "sequences"


Take another look at the last sequence in the previous section:

  • Find the next term in the following sequence:  1, 4, 8, 13, 19, 26,...
    • ( 1/2 )(7)2 + ( 3/2 )(7) 1 = 49/2 + 21/2 1 = 34

The formula we found for the terms was a bit messy, what with the fractions. But the row of first differences points out a simpler rule. Each next term was gotten by adding a growing amount to the previous term.

To get the second term, they added 3 to the first term; to get the third term, they added 4 to the second term; to get the fourth term, they added 5 to the third term; and so on. The rule, in mathematical vocabulary, was "To get the n-th term, add n+1 to the (n1)-th term." In table form, it looks like this:

n an change an+1
1 1 +3 4
2 4 +4 8
3 8 +5 13
4 13 +6 19
5 19 +7 26
6 26 +8 34

This sort of sequence, where you get the next term by doing something to the previous term, is called a "recursive" sequence. In the last case above, we were able to come up with a regular formula (a "closed form expression") for the sequence; this is often not possible (or at least not reasonable) for recursive sequences, which is why you need to keep them in mind as a difference class of sequences.

Probably the most famous recursive sequence is the Fibonacci sequence (pronounced "fibb - uh - NAH - chee" sequence). It is defined like this:

    a1 = 1
    a2 = 1

    an = an1 + an2
      for n > 2

That is, the first two terms are each defined to have the value of 1. (These are called "seed" values.) Then the third term is the sum of the previous two terms, so a3 = 1 + 1 = 2. Then the fourth term is the sum of the second and the third, so a4 = 1 + 2 = 3. And so forth. The first few terms are:

    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,...

While recursive sequences are easy to understand, they are difficult to deal with, in that, in order to get, say, the thirty-nineth term in this sequence, you would first have to find terms one through thirty-eight. There isn't a formula into which you could plug n = 39 and get the answer. (Well, there is, but its development is likely far beyond anything you've yet been trained to do.) For instance, if you try to find the differences, you'll get this:

      Fibonacci sequence differences

As you can see, you're not going to get a row of differences where all the entries are the same. However, you should notice that the sequence repeats itself in the lower rows, but shifted over to the right. And, in the beginning of each lower row, you should notice that a new sequence is starting: first 0; then 1, 0; then 1, 1, 0; then 2, 1, 1, 0; and so on. This is characteristic of "add the previous terms" recursive sequences. If you see this kind of behavior in the rows of differences, you should try finding a recursive formula.   Copyright Elizabeth Stapel 2002-2011 All Rights Reserved

Recursive sequences can be hard to figure out, so generally they'll give you fairly simple ones of the "add a growing amount to get the next term" or "add the last two or three terms together" type:

  • Find the next number in the sequence:  3, 2, 5, 7, 12, ...

    The first two values appear to be seed values, and then I'm adding the last two terms to get the next term:

n an2 an1 adding an
1       3
2   3     2
3 3 2 3 + 2 5
4 2 5 2 + 5 7
5 5 7 5 + 7 12

    If I'm right about the rule, then the next term would be:

      7 + 12 = 19

By the way, the differences look like this:

    rows of differences

Note how the sequence terms are repeated in lower rows, but shifted to the right, and how the new sequence terms are entering from the left.

  • Find the next term in the sequence:  1, 2, 2, 4, 8, 11, 33, 37, 148, ...

    This one is harder (and is not, strictly speaking, recursive). Take a look at the differences:

      table of differences

    As you can see, we're getting nothing useful from this table of differences. The rule here is not consistent:

      n an1 rule an
      1        1
      2 1 + 1 2
      3 2 1 2
      4 2 + 2 4
      5 4 2 8
      6 8 + 3 11
      7 11 3 33
      8 33 + 4 37
      9 37 4 148

    Then the next term will be "add five":

      148 + 5 = 153

As the above example shows, even the table of differences might not help with a recursive sequence. But don't be discouraged if it takes a while to find a formula or a pattern. If the sequence is mathematical, then it should be possible, eventually, to find some sort of an answer. The next section demonstrates some solutions.

<< Previous  Top  |  1 | 2 | 3 | 4 | 5 | 6 | 7  |  Return to Index  Next >>

Cite this article as:

Stapel, Elizabeth. "Finding the Next Number in a Sequence: Recursive Sequences."
    Purplemath. Available from 
http://www.purplemath.com/modules/nextnumb3.htm.
    Accessed
 

 



Purplemath:
  Linking to this site
  Printing pages
  School licensing


Reviews of
Internet Sites:
   Free Help
   Practice
   Et Cetera

The "Homework
   Guidelines"

Study Skills Survey

Tutoring from Purplemath
Find a local math tutor


This lesson may be printed out for your personal use.

Content copyright protected by Copyscape website plagiarism search

  Copyright 2002-2012  Elizabeth Stapel   |   About   |   Terms of Use

 

 Feedback   |   Error?