Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

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.

share|improve this answer
    
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 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}

share|improve this answer
1  
Hi, thanks for your answer, but this is not the approach we learned in the class. its good for my knowledge but "on the paper" they want the way Robart wrote to me. I just dont know how to continue, I wrote him down the equation I have got. again, thanks. –  user2976686 May 5 at 15:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.