A Recursive Sequence is a function that refers back to itself. Below are several examples of recursive sequences.
For instance, $$ {\color{red}f}(x) = {\color{red}f}(x-1) + 2 $$ is an example of a recursive sequence because $$ {\color{red}f}(x)$$ defines itself using $$ {\color{red}f}$$.
Visualization of a Recursive sequence
Pascal's Triangle is one of the most famous recursive sequences in mathematics. Below is a visualization of how Pascal's Triangle works. As you can see each term in the triangle is a result of adding two other 'parts' of the triangle.
See more math gifs here
Recursive sequences often cause students a lot of confusion. Before going into depth about the steps to solve recursive sequences, let's do a step-by-step examination of 2 example problems. After that, we'll look at what happened and generalize the steps.
Example 1
Calculate $$ f(7) $$ for the recursive sequence $$ f(x) = 2 \cdot f(x - 2) + 3 $$ which has a seed value of $$ f(3) = 11 $$.
Example 2
Calculate $$ f(8)$$ for the recursive sequence $$ f(x) = 4 \cdot f(x - 3) + 1 $$ which has a seed value of $$f(2) = 9 $$.
The Two "Phases" of solving recursion problems
Let's explore the two phases of solving recursive sequences:
- Phase I: Re-subsitute values into $$ f(x) $$ until you reach the "seed value" (in programming it's often called the "base case").
- Part II: Once you reach the Seed Value you start resubstituting values into the earlier expressions (back up the chain). The key here is is that you are substituting actual numbers/values now.
Can you determine why the sequence below is 'unsolvable'?
Look at the problem step by step to see why you can not solve this problem.
Example 3
This example is one of the most famous recursive sequences and it is called the Fibonacci sequence. It also demonstrates how recursive sequences can sometimes have multiple $$ f(x)$$'s in their own definition.
It is defined below.
$$ f(x) = f(x-1) + f(x-2) $$
Practice Problem 1
Keep re-substituting until you reach the seed value ($$ f({\color{red}4}) = {\color{blue}2}$$).
We hit the 'seed' value so we are done with the first "phase".
Substitute back up the "chain" using actual values.
Below is the step by step work:
$$ \boxed{ f({\color{red}6}) = 2\cdot f({\color{red}5})+3 \\ f({\color{red}6}) = 2 \cdot {\color{blue}7} +3 = {\color{blue}17} } \\ \boxed{ f({\color{red}5}) = 2\cdot f({\color{red}4}) +3 \\ f({\color{red}5}) = 2 \cdot {\color{blue}2} +3 = {\color{blue}7} } \\ \boxed{ f({\color{red}4}) = {\color{blue}2} } $$Practice Problem 2
Keep re-substituting until you reach the seed, value ($$ f({\color{red}12}) = {\color{blue}-4}$$).
We hit the 'seed' value so we are done with the first "phase".
Substitute back up the "chain" using actual values.
Below is the step by step work.
$$ \boxed{ f({\color{red}8}) = 5\cdot f({\color{red}10}) - 3 \\ f({\color{red}8}) = 5\cdot {\color{blue}-23} - 3 = -93 } \\ \boxed{ f({\color{red}10 }) = 5\cdot f({\color{red}12}) - 3 \\ f({\color{red}10 }) = 5\cdot {\color{blue}-4} - 3= -23 } \\ \boxed{ f({\color{red}12}) = {\color{blue}-4} } $$Practice Problem 3
Keep re-substituting until you reach the seed value ($$ f({\color{red}0}) = {\color{blue}2}$$).
We hit the 'seed' value so we are done with the first "phase".
Substitute back up the "chain" using actual values.
Below is the step by step work:
$$ f({\color{red}x+1}) = -2\cdot f({\color{red}x}) + 3 \\ \boxed{ f({\color{red}2}) = -2 \cdot f({\color{red}1} + 3) \\ f({\color{red}2}) = -2 \cdot ({\color{blue}-1}) + 3 = 5 } \\ \boxed{ f({\color{red}1}) = -2 \cdot f({\color{red}0}) + 3 \\ f({\color{red}1}) = -2 \cdot {\color{blue}2} + 3 = -1 } \\ \boxed{ f({\color{red}0}) = {\color{blue}2} } $$Practice Problem 4
Keep re-substituting until you reach the seed value ($$ f({\color{red}1}) = {\color{blue}5}$$).
We will never hit the 'seed' value so this problem cannot be solved.