Recursion

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

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

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
1. Phase I: Re-subsitute values into $$f(x)$$ until you reach the "seed value" (in programming it's often called the "base case")
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.

Can you determine why the sequence below is 'unsolvable'?

Look at the problem step by step to see why you cannot 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)$$
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} }$$
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} }$$
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 } }$$
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.

Ultimate Math Solver (Free)

Free Algebra Solver ... type anything in there!