# Proving Recurrence Relation By Forward Substitution

I'm having trouble understanding the inductive proof of the following recurrence relation by forward substitution. I get that were plugging in the value for our induction step into the relation but I don't get how $n ^{2.585}$ is ultimately derived.

Using the relationship T(n) = 6T(n/2) for n>1.

T(2) = 6T(2/2) = 6T(1) = 6

T(4) = 6T(4/2) = 6T(2) = 36

T(8) = 6T(8/2) = 6T(4) = 216

We find lg 2=1, lg 4=2, lg 8=3.

So the relationship is T(n)= $6^{lgn}$.

Induction base: For n = 1 we have initial condition

T(1) = $6^{lg1}$ = $6^0$ = 1

Induction hypothesis: Assume, for arbitrary n>1, n being a power of 2, that

T(n)= $6^{lgn}$

Induction step: Show induction hypothesis also true for the next step 2n (each step doubles n)

T(2n) = $6 ^{lg (2n)}$

To show next step, we replace n with 2n in the recurrence T(n)=6T(n/2) and use the hypothesis T(n) = $6 ^{lg n}$ , we get:

T(2n) = 6T((2n)/2) = 6T(n) = 6 . $6^{lgn}$ = $6 ^{1 + lg n}$ = $6 ^{lg 2 + lg n}$ = $6 ^{lg(2n)}$

QED

So, T (n) = $6 ^{lgn}$ = $n ^{lg6}$ = $n ^{2.585}$ Solution for the above recurrence for T(n) turns out to be $O(^{n2.585})$

• The log are of base 2. Apr 29, 2016 at 2:14

$$\large 6^{\lg n}=\left(2^{\lg 6}\right)^{\lg n}=2^{(\lg 6)(\lg n)}=2^{\lg \left(n^{\lg 6}\right)}=n^{\lg 6}$$
• For more symmetry you could either replace the penultimate term $2^{\lg \left(n^{\lg 6}\right)}$ by $\left(2^{\lg n}\right)^{\lg 6}$, or replace the second term $\left(2^{\lg 6}\right)^{\lg n}$ by $2^{\lg \left(6^{\lg n}\right)}$ Sep 29, 2019 at 15:15