Hi all, thanks in advance for any help.

 

This is the question:

 

Solve the following recurrence relation by forward substitution and then verify the result by mathematical induction:

 

T(n) = 2T(n/7) for n > 1, n is a power of 7

T(1) = 1

 

My answer:

 

T(7) = 2T(7/7) = 2T(1) = 2

T(14) = 2T(14/7) = 2T(2) = 2^2

T(21) = 2T(21/7) = 2T(3) = 2^3

T(28) = 2T(28/7) = 2T(4) = 2^4

 

(I'm not sure if going up in 7's is correct)

 

Solution for recurrence relation: T(n) = 2^log n

 

T(1) = 2^log 1 = 2^0 = 1

T(2n) = 2T(2n/2) = 2T(n) = 2^1 x 2^log n

= 2^ log 2n

 

Check answer for T(14) = 2^2

 

2^log n = 2^log 14 = 2^7^2 (two to the power of 7 squared) = 2^7log2 = 2^2

 

I managed to do this because of an example given, I don't know if its correct. I would appreciate if somebody could check/walk through each stage. Thanks again.

A power of 7 is not a multiple of 7.

They go like: 1, 7, 49, 343...