<img src="https://d5nxst8fruw4z.cloudfront.net/atrk.gif?account=iA1Pi1a8Dy00ym" style="display:none" height="1" width="1" alt="" />
Dismiss
Skip Navigation
Our Terms of Use (click here to view) and Privacy Policy (click here to view) have changed. By continuing to use this site, you are agreeing to our new Terms of Use and Privacy Policy.

Recursive Formulas

Where a term is based on prior term(s) in a sequence.

Atoms Practice
Estimated20 minsto complete
%
Progress
Practice Recursive Formulas
Practice
Progress
Estimated20 minsto complete
%
Practice Now
Recursion

When you look at a pattern, there are many ways to describe it. You can describe patterns explicitly by stating how each term \begin{align*}a_k\end{align*}ak is obtained from the term number \begin{align*}k\end{align*}k. You can also describe patterns recursively by stating how each new term \begin{align*}a_k\end{align*}ak is obtained from the previous term \begin{align*}a_{k-1}\end{align*}ak1. Recursion defines an entire sequence based on the first term and the pattern between consecutive terms. The Fibonacci sequence is a famous recursive sequence, but how is it represented using recursion?

\begin{align*}0,1,1,3,5,8,13,21,34, \ldots\end{align*}0,1,1,3,5,8,13,21,34,

Finding Terms with Recursion

When most people see a pattern they see how consecutive terms are related to one another. You might describe patterns with phrases like the ones below:

Pattern Recursive Description
\begin{align*}3,6,12,24, \ldots\end{align*}3,6,12,24, “Each term is twice as big as the previous term”
\begin{align*}3,6,9,12, \ldots\end{align*}3,6,9,12, “Each term is three more than the previous term”

Each phrase is a sign of recursive thinking that defines each term as a function of the previous term.

\begin{align*}a_k=f(a_{k-1})\end{align*}ak=f(ak1)

In some cases, a recursive formula can be a function of the previous two or three terms. Keep in mind that the downside of a recursively defined sequence is that it is impossible to immediately know the \begin{align*}100^{th}\end{align*}100th term without knowing the \begin{align*}99^{th}\end{align*}99th term.

In order to write a recursive definition for a sequence you must define the pattern and state the first term.  With this information, others would be able to replicate your sequence without having seen it for themselves. Take the following sequence:

\begin{align*}3,7,11,15,18, \ldots\end{align*}3,7,11,15,18,

The first term is : \begin{align*}a_1=3\end{align*}a1=3

Notice that each of the following terms increases by 4 so the recursive piece of the sequence is : \begin{align*}a_k=a_{k-1}+4\end{align*}ak=ak1+4. Putting the two together gives you the recursive definition of the sequence:

\begin{align*}a_1=3\end{align*}a1=3

\begin{align*}a_k=a_{k-1}+4\end{align*}ak=ak1+4

A recursive definition must always have two parts, the base case(the starting number) and the recursive case (the pattern to get more terms). Note that the base case may include more than one statement as is the case with the Fibonacci sequence.

    

Examples

Example 1

The Fibonacci sequence is represented by the recursive definition:

\begin{align*}a_1=0\end{align*}a1=0

\begin{align*}a_2=1\end{align*}a2=1

\begin{align*}a_k =a_{k-2}+a_{k-1}\end{align*}ak=ak2+ak1

The first eleven terms and the sum of these terms is:

\begin{align*}0+1+1+2+3+5+8+13+21+34+55=143\end{align*}0+1+1+2+3+5+8+13+21+34+55=143

Example 2

What are the first nine terms of the sequence defined by:

\begin{align*}a_1=1\end{align*}a1=1

\begin{align*}a_k =\frac{1}{k}+1?\end{align*}ak=1k+1?

\begin{align*}1, 2, \frac{3}{2}, \frac{5}{3}, \frac{8}{3}, \frac{13}{8}, \frac{21}{13}, \frac{34}{21}, \frac{55}{34}\end{align*}1,2,32,53,83,138,2113,3421,5534

Example 3

The Lucas sequence is like the Fibonacci sequence except that the starting numbers are 2 and 1 instead of 1 and 0. What are the first ten terms of the Lucas sequence?

\begin{align*}2,1,3,4,7,11,18,29,47,76 \end{align*}2,1,3,4,7,11,18,29,47,76

Example 4

Zeckendorf’s Theorem states that every positive integer can be represented uniquely as a sum of nonconsecutive Fibonacci numbers. What is the Zeckendorf representation of the number 50 and the number 100?

\begin{align*}50=34+13+3;\ 100=89+8+3\end{align*}50=34+13+3; 100=89+8+3

Example 5

Consider the following pattern generating rule:

If the last number is odd, multiply it by 3 and add 1.

If the last number is even, divide the number by 2.

Repeat.

Try a few different starting numbers and see if you can state what you think always happens.

You can choose any starting positive integer you like. Here are the sequences that start with 7 and 15. 

\begin{align*}7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1\ldots \end{align*}7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1

\begin{align*}15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1,4,2,1\ldots\end{align*}15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1,4,2,1

You could make the conjecture that any starting number will eventually lead to the repeating sequence 4, 2, 1.

This problem is called the Collatz Conjecture and is an unproven statement in mathematics. People have used computers to try all the numbers up to \begin{align*}5\times2^{60}\end{align*}5×260 and many mathematicians believe it to be true, but since all natural numbers are infinite in number, this test does not constitute a proof.

Review

Write a recursive definition for each of the following sequences.

1. \begin{align*}3,7,11,15,19,\ldots\end{align*}3,7,11,15,19,

2. \begin{align*}3,9,27,81,\ldots\end{align*}3,9,27,81,

3. \begin{align*}3,6,9,12,15,\ldots\end{align*}3,6,9,12,15,

4. \begin{align*}3,6,12,24,48,\ldots\end{align*}3,6,12,24,48,

5. \begin{align*}1,4,16,64,\ldots\end{align*}1,4,16,64,

6. Find the first 6 terms of the following sequence:

\begin{align*}b_1=2\end{align*}b1=2

\begin{align*}b_2=8\end{align*}b2=8

\begin{align*}b_k =6b_{k-1}-4b_{k-2}\end{align*}bk=6bk14bk2

7. Find the first 6 terms of the following sequence:

\begin{align*}c_1=4\end{align*}c1=4

\begin{align*}c_2=18\end{align*}c2=18

\begin{align*}c_k =2c_{k-1}+5c_{k-2}\end{align*}ck=2ck1+5ck2

Suppose the Fibonacci sequence started with 2 and 5.

8. List the first 10 terms of the new sequence.

9. Find the sum of the first 10 terms of the new sequence.

Write a recursive definition for each of the following sequences. These are trickier!

10. \begin{align*}1,4,13,40,\ldots\end{align*}1,4,13,40,

11. \begin{align*}1,5,17,53,\ldots\end{align*}1,5,17,53,

12. \begin{align*}2,11,56,281, \ldots\end{align*}2,11,56,281,

13. \begin{align*}2,3,6,18,108,\ldots\end{align*}2,3,6,18,108,

14. \begin{align*}4,6,11,18,30,\ldots\end{align*}4,6,11,18,30,

15. \begin{align*}7,13,40,106,292,\ldots\end{align*}7,13,40,106,292,

Review (Answers)

To see the Review answers, open this PDF file and look for section 12.1. 

Vocabulary

common difference

Every arithmetic sequence has a common or constant difference between consecutive terms. For example: In the sequence 5, 8, 11, 14..., the common difference is "3".

common ratio

Every geometric sequence has a common ratio, or a constant ratio between consecutive terms. For example in the sequence 2, 6, 18, 54..., the common ratio is 3.

index

The index of a term in a sequence is the term’s “place” in the sequence.

recursive

The recursive formula for a sequence allows you to find the value of the nth term in the sequence if you know the value of the (n-1)th term in the sequence.

recursive formula

The recursive formula for a sequence allows you to find the value of the nth term in the sequence if you know the value of the (n-1)th term in the sequence.

sequence

A sequence is an ordered list of numbers or objects.

Image Attributions

Explore More

Sign in to explore more, including practice questions and solutions for Recursive Formulas.
Please wait...
Please wait...