﻿ How to solve recursive sequences in Math, practice problems explained step by step with examples # 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}$$.

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