Recurrence Relation: Solve T(n) = 25T(n/5) + ((n log 5) / (log n))^2

Question

T(n) = 25T(n/5) + ((n log 5) / (log n))^2

I am new to recurrence relation and was stuck on solving this above question and would like to seek some direction!

I do not think that I am able to apply master theorem here which leads me to use the telescoping series where I was able to reduce the relation (by dividing by n^2 log^2 5) to the form of T(n) = T(1)/1 + (1/2)^2 + (1/4)^2 + ... + (1/logn)^2. After which I was not able to further simplify further.

Appreciate any advice!

Answer 1

Hint.

After n = 5^mthe recurrence can be recast as

r[m] = 25*r[m-1]+(5^m/m)^2

now this is a linear and the solution can be obtained as

r[n] = rh[m] + rp[m]

The homogeneous has the solution

rh[m] = 5^(2*m)c0

and to obtain a particular solution we proceed by considering

rp[m] = 5^(2*m)c0[m]

and after substitution

5^(2*m)c0[m] = 5^2*5^(2*(m-1))c0[m-1] + (5^(2*m)/m)^2

or simplifying

c0[m] = c0[m-1] + 1/m^2

with solution

c0[m] = pi^2/6 - PolyGamma[1,1,m]

then

rp[m] = 5^(2*m)*(pi^2/6 - PolyGamma[1,1,m])

and finally

r[m] = (pi^2/6 - PolyGamma[1,1,m] + c0)*5^(2*m)

the backwards step needed to obtain T[n] is left to the reader.