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").
![phase of I of recursion example 2]()
-
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.
![Recursion Phase 2 example 1]()
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
Phase I
Keep re-substituting until you reach the seed value ($$ f({\color{red}4}) = {\color{blue}2}$$).
$$
f({\color{red}x}) = 2\cdot f({\color{red}x-1}) +3
\\
\boxed{
f({\color{red}6}) = 2\cdot f({\color{red}6 -1})+3
\\
f({\color{red}6}) = 2\cdot f({\color{red}5})+3
}
\\
\boxed{
f({\color{red}5}) = 2\cdot f({\color{red}5 -1})+3
\\
f({\color{red}5}) = 2\cdot f({\color{red}4}) +3
}
\\
\boxed{
f({\color{red}4}) = {\color{blue}2}
}
$$
We hit the 'seed' value so we are done with the first "phase".
Phase 2
Substitute back up the "chain" using actual values.
$$
\boxed{
f({\color{red}6}) = {\color{blue}17}
}
$$
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
Phase I
Keep re-substituting until you reach the seed, value ($$ f({\color{red}12}) = {\color{blue}-4}$$).
$$
f({\color{red}x}) = 5\cdot f({\color{red}x + 2}) -3
\\
\boxed{
f({\color{red}8}) =5 \cdot f({\color{red}8+2}) - 3
\\
f({\color{red}8}) = 5\cdot f({\color{red}10}) - 3
}
\\
\boxed{
f({\color{red}10 }) = 5\cdot f({\color{red}10+2}) - 3
\\
f({\color{red}10 }) = 5\cdot f({\color{red}12}) - 3
}
\\
\boxed{
f({\color{red}12 }) = {\color{blue}-4}
}
$$
We hit the 'seed' value so we are done with the first "phase".
Phase 2
Substitute back up the "chain" using actual values.
$$
\boxed{
f({\color{red}8 }) = {\color{blue}-118}
}
$$
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 = -118 } \\ \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
Phase I
Keep re-substituting until you reach the seed value ($$ f({\color{red}0}) = {\color{blue}2}$$).
$$
f({\color{red}x+1}) = -2\cdot f({\color{red}x}) + 3
\\
\boxed{
f({\color{red}2}) = f({\color{red}1+1})
\\
\text{Therefore} f({\color{red}x+1}) = f(2)
\\
\text{and} f({\color{red}x}) =f(1)
\\
f({\color{red}2}) = -2 \cdot f({\color{red}1}) + 3
}
\\
\boxed{
f({\color{red}1}) = f({\color{red}1 + 0})
\\
\text{Therefore} f({\color{red}x+1}) = f(1)
\\
\text{and } f({\color{red}x}) = f(0)
\\
f({\color{red}1}) = -2 \cdot f({\color{red}0}) + 3
}
\\
\boxed{
f({\color{red}0 }) = {\color{blue}2}
}
$$
We hit the 'seed' value so we are done with the first "phase".
Phase 2
Substitute back up the "chain" using actual values.
$$
\boxed{
f({\color{red}2}) = {\color{blue}5}
}
$$
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
Phase I
Keep re-substituting until you reach the seed value ($$ f({\color{red}1}) = {\color{blue}5}$$).
$$
\boxed{
f({\color{red}3}) =f({\color{red}3-2})+11
\\
f({\color{red}3}) =f({\color{red}1})+11
}
\\
\boxed{
f({\color{red}1}) =f({\color{blue}5})
}
$$
We hit the 'seed' value so we are done with the first "phase".
Phase 2
Substitute back up the "chain" using actual values.
$$
\boxed{
f({\color{red}1}) = {\color{blue}5}
}
$$
Below is the step by step work:
$$ \boxed{ f({\color{red}3}) =f({\color{red}1})+11 \\ f({\color{red}3}) ={\color{blue}5}+11 } \\ \boxed{ f({\color{red}3}) ={\color{blue}16} } $$
