Find general solution

Question

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

Answer 1

Hint: plug in $t_k = a \cdot 2^k + (b k + c) \cdot 16^k$, $t_{k-1} = \dfrac{a}{2} \cdot 2^k + \dfrac{b k - b + c}{16} \cdot 16^k$ to the recurrence, and see what constants $a,b,c$ make this work.

Answer 2

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}