<s>[INST] Find general solution I want to find the general solution for the following :
$$t(n)=t(\frac{n}{4})+\sqrt{n}+n^2+n^2log_{8}n $$ Note: $n=4^k$
$t(n)=t(4^k)=t_{k}$
$$t_{k}=t_{k-1}+2^k+16^k\cdot \frac{2}{3}k$$
$$\rho(x)=(x-1)(x-2)(x-16)^2$$
There is problem to find the coefficients, any advice? thanks
 [/INST] As you state, the change of variable $n = 4^k$ and $t(4^k) = t_k$ reduces the recurrence to:
$$
t_{k + 1} = t_k + 2 \cdot 2^k + 16 \cdot 16^k + \frac{32 k}{3} \cdot 16^k
$$
Define the generating function:
$$
T(z) = \sum_{k \ge 0} t_k z^k
$$
multiply the recurrence by $z^k$, sum over $k \ge 0$, and recognize a few sums,
like:
$$
\sum_{k \ge 0} k a^k z^k
  = z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - a z}
  = \frac{a z}{(1 - a z)^2}
$$
to get:
$$
\frac{T(z) - t_0}{z}
  = T(z)
      + 2 \cdot \frac{1}{1 - 2 z}
      + 16 \cdot \frac{1}{1 - 16 z}
      + \frac{32}{3} \cdot \frac{16 z}{(1 - 16 z)^2}
$$
Solve as partial fractions:
$$
T(z)
  = \frac{32}{45} \cdot \frac{1}{(1 - 16 z)^2}
      - \frac{272}{675} \cdot \frac{1}{1 - 16 z}
      + 2 \cdot \frac{1}{1 - 2 z}
      + \frac{675 t_0 - 1558}{675} \cdot \frac{1}{1 - z}
$$
Now use the generalized binomial theorem:
$$
(1 + u)^{-m} 
  = \sum_{k \ge 0} \binom{-m}{n} u^k
  = \sum_{k \ge 0} (-1)^k \binom{k + m - 1}{m - 1} u^k
$$
in particular:
$$
\binom{-2}{k} = (-1)^k(k + 1)
$$
to finish this off:
\begin{align}
t_k
  &= \frac{32}{45} (k + 1) \cdot 16^k
       - \frac{272}{675} \cdot 16^k
       + 2 \cdot 2^k
       + \frac{675 t_0 - 1558}{675} \\
  &= \frac{32}{45} \cdot k \cdot 16^k 
       + \frac{208}{675} \cdot 16^k
       + 2 \cdot 2^k
       + \frac{675 t_0 - 1558}{675} \\
t(n)
  &= \frac{32}{45} n^2 \log_4 n
       - \frac{272}{675} n^2
       + 2 \sqrt{n}
       + \frac{675 t_0 - 1558}{675}
\end{align}
</s>