Solve the following recurrence relation for n and prove that

Solve the following recurrence relation for n and prove that your solution is correct by induction.

Solve the following recurrence relation for n and prove that your solution is correct by induction. f(n) = {4 n = 1 f(n/4) + 2 n > 1

f(n) = f(n/4) + 2 , f(1) = 4

f(4)=6

f(16)=8

putting n = 4k,

we get

f(4k) -f(k) = 2

this recurrenc eequation solution is

f(n) = (log n)/(log 2)+4

we have to prove this solution satisfy

f(4n)- f(n)= 2

now

f(4n)- f(n)=

((log 4n)/(log 2)+4) - ((log n)/(log 2)+4)

= ((log 4n ) - (log n) )/ (log 2)

= (log 4 + log n - log n)/(log 2

= log 4/ log 2

= 2