# Solve Recurrence Relation Using Iteration/Substitution Method

Iteration/Substitution Method

The **Iteration Method**, is also known as the **Iterative Method**, **Backwards Substitution**, **Substitution Method**, and **Iterative Substitution**. It is a technique or procedure in computational mathematics used to solve a recurrence relation that uses an initial guess to generate a sequence of improving approximate solutions for a class of problems, in which the n-th approximation is derived from the previous ones.

Let’s take a look at a recurrence relation problem and try to solve it. By solve it, here I mean get it in a “**closed form**” . A **Closed**-**Form** Solution is an equation that solves a given problem in terms of functions and mathematical operations from a given generally-accepted set. For example, an infinite sum would generally not be considered **closed**-**form**.

Let’s start with the recurrence relation, T(n) = 2 * T(n/2) + 2, and try to get it in a closed form. Note that **‘T’ **stands for time, and therefore **T(n) **is a function of time that takes in input of size **‘n’**.

T(n) = 2T(n/2) + 2

This is our first iteration, we will name our iterations as ‘**k**’ such that the first iteration means **k=1**, and the second means **k=2** and so on. The ‘**k**’ value will be used later.

Now we need to figure out what **T(n/2) **is. We can do that by taking “n/2” , and putting it into our original function **T(n)**, to get the following:

Note: We are just replacing** n** with** n/2**.

T(n/2) = 2T( (n/2) / 2) + 2

= **2T( n/4 ) + 2**

**So our original equation looks like the following when k= 2**

T(n) = 2T(n/2) + 2

= 2( **2T( n/4 ) + 2**) + 2

= 4T(n/4) + 4 + 2

That was our second iteration, so this means **k=2** .Now we must figure out what **T(n/4)** is. We can do that by taking “n/4” , and putting it into our original function **T(n)**, to get the following:

T(n/4) = 2T( (n/4) / 2 ) + 2

= **2T(n/8) + 2**

**So our original equation looks like the following when k=3**

T(n) = 4T(n/4) + 4 + 2

= 4(**2T(n/8) + 2**) + 4 + 2

= 8T(n/8) + 8+ 4 + 2

That was our third iteration, so this means **k=3** . Now we must figure out what **T(n/8)** is. We can do that by taking “n/8” , and putting it into our original function **T(n)**, to get the following:

T(n/8) = 2T( (n/8) / 2 ) + 2

= **2T(n/16) + 2**

**So our original equation looks like the following when k=4**

T(n) = 8T(n/8) + 8+ 4 + 2

=8(**2T(n/16) + 2**) + 8+ 4 + 2

= 16T(n/16)+16 + 8+ 4 + 2

That was our fourth iteration, so this means **k=4** . Now we must figure out what **T(n/16)** is. We can do that by taking “n/8” , and putting it into our original function **T(n)**, to get the following:

T(n/16) = 2T( (n/16) / 2 ) + 2

= **2T(n/32) + 2**

**So our original equation looks like the following when k=5**

T(n) = 16T(n/16)+16 + 8+ 4 + 2

=16(**2T(n/32) + 2**)+16 + 8+ 4 + 2

= 32T(n/32)+ 32 +16 + 8+ 4 + 2

Okay let’s stop here and see if we can see a pattern, if not then you should continue this method or process until you do.

When k=1, we had T(n) = 2T(n/2) + 2

When k=2, we had T(n) = 4T(n/4) + 4 + 2

When k=3, we had T(n) = 8T(n/8) + 8+ 4 + 2

When k=4, we had T(n) = 16T(n/16)+16 + 8+ 4 + 2

When k=5, we had T(n) = 32T(n/32)+ 32 +16 + 8+ 4 + 2

Let’s rewrite this a little bit more to see if we can see a pattern.

**When k=1, we had T(n) = 2T(n/2) + 2**

= T(n) = 2T(n/2) + 2 →T(n) = 2T(n/2) + 2(1)

**When k=2, we had T(n) = 4T(n/4) + 4 + 2**

= T(n) = 4T(n/4) + 4 + 2 → T(n) = 4T(n/4) + 2(2 + 1)

**When k=3, we had T(n) = 8T(n/8) + 8+ 4 + 2**

= T(n) = 8T(n/8) + 8+ 4 + 2 → T(n) = 8T(n/8) + 2( 4 + 2 +1)

**When k=4, we had T(n) = 16T(n/16)+16 + 8+ 4 + 2**

= T(n) = 16T(n/16)+16 + 8+ 4 + 2 → T(n) = 16T(n/16)+2(8+ 4 + 2 +1)

**When k=5, we had T(n) = 32T(n/32)+ 32 +16 + 8+ 4 + 2**

=T(n) = 32T(n/32)+ 32 +16 + 8+ 4 + 2

= T(n) = 32T(n/32)+ 2 (16 + 8+ 4 + 2 + 1)

**Notice the general form in terms of ‘k’ looks like:**

T(n) = 2^k * T(n/ (2^k) + 2 *Summation from i=0 to k-1 of 2^i

**The summation from i=0 to k-1 of 2^i is 2^(k) — 1.So our general form looks like below:**

T(n) = 2^k * T(n/ (2^k) )+ 2 *(2^k — 1)

T(n) = 2^k * T(n/ (2^k) )+ 2^(k+1) — 2

When does our recurrence relation stop ? Well it stops when T(n/(2^k)) hits the base case. You may say, but we were never given a base case. That’s okay because every recurrence relation has a base case, and it is always some constant value. So if a base case isn’t provided, we can make one up. So our base case will be **T(1) = C**, which means when our input is of size 1, the time it takes to execute the function ‘**T**’ is ‘**C**’ unit(s) of time, where ‘**C**’ is some constant unit of time. This means when n = 1, T(n=1) = C.

We must now get our T(n) function from our general form to stop, and therefore need T(n/(2^k))=C, this implies n/(2^k) must equal 1, since T(n/(2^k)=1) = C. **Let’s do some algebra below.**

= n/(2^k) = 1

= n = (2^k)

= log base 2 of n = k

We now not only have our stopping case, but can also put our value ‘k’ in terms of n, for the entire equation, by plugging in ‘log base 2 of n’ for ‘k’.

T(n) = 2^(log base 2 of n) * T(n/ (2^(log base 2 of n)) )+ 2 *(2^(log base 2 of n) — 1)

T(n) = n * T(n/n) + 2( n — 1)

T(n) = n T(1) + 2n — 2

T(n) = n*(C) + 2n — 2

T(n) = Cn + 2n — 2

T(n) = n ( C+2) — 2

So our guess is that the closed form of our recurrence relation is:**T(n) = n ( C+2) — 2, where C is some constant**

**NOTE:** n ( C+2) — 2 is O(n)

If C = 0 then the equation is

T(n) = n(0 + 2) — 2

T(n) = 2n — 2 = 2( n-1)

Because the closed form is a guess we need to show that our guess is correct and to do that we can use **Mathematical Induction**.

There are many places to learn more about recurrence relation online, and at school. I have a course on Udemy.com called “Recurrence Relation Made Easy” where I help students to understand how to solve recurrence relations and asymptotic terms such as Big-O, Big Omega, and Theta, be sure to check it out !

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )