# 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

-

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.
that's what I got: $$c_{2}9^k + c_{3}k9^k +c_{4}3^k = c_{2}9^{k-1}+c_{3}k9^{k-1}-c_{3}9^{k-1}+c_{4}3^{k-1}+k9^k + 3^k$$ what now? – user2976686 May 5 '14 at 15:18
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}