Solving Recurrence Solve $\ T(n)= n^2/2* T(n/2)+n^4/8*T(n/4),T(1)=T(2)=1 $

Question

Well... I've tried hard...

The problem is Solve $\ T(n)= n^2/2* T(n/2)+n^4/8*T(n/4),T(1)=T(2)=1 $ for all values of n that is a power of 2.

Actually, I do only know that I can let $\ n=2^m$ ...However, I have no idea than:(

Answer 1

Let $n=2^m$ and $a_m=T(2^m).$ Then $$ a_m = 2^{2m-1}a_{m-1}+2^{4m-3}a_{m-2} \;\;,\;\; a_0 = 1,\;a_1=1 $$ When we calculate the first few elements $a_0,a_1,\ldots,$ it appears as if $a_m=2^{m^2-1}b_m$ with a suitable sequence $b_0,b_1,\ldots$

When we perform this substitution, we get $$ 2^{m^2-1}b_m = 2^{2m-1}2^{(m-1)^2-1}b_{m-1}+2^{4m-3}2^{(m-2)^2-1}b_{m-2} \;\;,\;\; b_0 = 2,\;b_1=1 $$ or $$ 2^{m^2-1}b_m = 2^{m^2-1}b_{m-1}+2^{m^2}b_{m-2}\;\;,\;\; b_0 = 2,\;b_1=1 $$ or $$ b_m = b_{m-1}+2b_{m-2}\;\;,\;\; b_0 = 2,\;b_1=1 $$ This is an ordinary homogeneous linear difference equation, which is equivalent to $$ b_m = 2^m+(-1)^m $$ Therefore, $$ T(2^m)=a_m=2^{m^2-1}b_m = 2^{m^2-1}\left(2^m+(-1)^m\right) $$