How to Solve Recursive Sequences

Recursion

Penjee.com, a site for teaching kids Python, has some excellent gifs on Recursion in programming including this one:

conceptual understanding of Recursion

What is a recursive Sequence?

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}$$ .
Examples of Recursive Math sequences

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 $$

loading powerpoint
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 $$

loading powerpoint

The Two "Phases" of solving recursion problems

Let's explore the two phases of solving recursive sequences
  1. 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
  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'?

unsolvable math recursion problem example

Look at the problem step by step to see why you cannot solve this problem.

loading powerpoint
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) $$
loading powerpoint
Practice Problem 1

Given the recursive sequence $$ f(x) = 2\cdot f(x-1) +3 $$ and $$ f( \color{red}{4}) = \color{blue}{2} $$ evaluate $$f(6) $$ .

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

Solve the recursive sequence $$ f(x) = 5\cdot f(x + 2 ) - 3 $$ and $$ f( \color{red}{ 12 }) = \color{blue}{-4} $$ calculate $$f(8) $$ .

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}{-93} } $$

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

If a sequence is defined recursively by $$ f(0) = 2 $$ and $$ f(x+1) = -2 \cdot f(x) +3 $$ for $$ x \ge 0$$, then solve for $$f(2) $$

This question was taken from Algebra I (Common Core) Regents exam from June 2015 (Question #20)
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

Solve the recursive sequence $$ f(x) = f(x - 2 ) + 11 $$ and $$ f( \color{red}{ 1 }) = \color{blue}{5} $$ calculate $$f(3) $$ .

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{red}{1}-2 )+11 \\ f( \color{red}{3}) =f( \color{red}{-1} )+11 } \\ \boxed{ \text{ \color{red} This is UNSOLVABLE} } $$ We will never hit the 'seed' value so this problem cannot be solved.

Pascals Triangle (recursive Sequence) How recursion works (programming) in 7 Gifs

Ultimate Math Solver (Free)

Free Algebra Solver ... type anything in there!