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:
||“Each term is twice as big as the previous term”|
||“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.
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:
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.
The Fibonacci sequence is represented by the recursive definition:
The first eleven terms and the sum of these terms is:
What are the first nine terms of the sequence defined by:
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?
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?
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.
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.
You could make the conjecture that any starting number will eventually lead to the repeating sequence 4, 2, 1.
Write a recursive definition for each of the following sequences.
6. Find the first 6 terms of the following sequence:
7. Find the first 6 terms of the following sequence:
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!
To see the Review answers, open this PDF file and look for section 12.1.