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 have the equation $T(n) = T(n-2) + n^5 + n$ for $n\ge2$.

I want to write $n$ in the form of $bk+r$. Thus $n=2k+r$ where $0\le r<2$, i.e. $r=0$ or $r=1$.

I have come to the conclusion that $T(n)$ follows the following formula:

$$\begin{align*}T(n) = T(r) &+ [(2+r)^5 + (2+r)] + [(2\cdot2+r)^5 + (2\cdot2+r)] + \ldots \\ &+ [(2i+r)^5 + (2i+r)] + \ldots + [(2k+r)^5 + (2k+r)]\end{align*}$$

However, I cannot tell determine what the rate of growth, i.e. the order of the function is, in terms of $n$. This is problem 5 in the pdf here.

That pdf also contains the formulas I've used to get thus far. Any help would be awesome. I can't seem to figure this out.

share|improve this question
    
Thank you @brian –  canton May 11 '12 at 10:13
    
You're welcome! –  Brian M. Scott May 11 '12 at 10:14
    
I get an error message when following the link to the pdf. –  Daan Michiels May 11 '12 at 10:16
    
@DaanMichiels I've updated the link. Let me know if there are still issues. Thank you for catching! –  canton May 11 '12 at 10:17
    
Ok, it works now. –  Daan Michiels May 11 '12 at 10:17
add comment

1 Answer

up vote 2 down vote accepted

I've given enough to allow you to get an exact closed expression for $T(n)$ if you want to do a lot of work, but if you're interested only in the order of the function, you can skip most of the details.

$$\begin{align*} T(n)&=T(r)+\sum_{i=1}^k\Big((2i+r)^5+(2i+r)\Big)\\ &=T(r)+\sum_{i=1}^k(2i+r)^5+\sum_{i=1}^k(2i+r)\\ &=T(r)+\sum_{i=1}^k(2i+r)^5+2\sum_{i=1}^ki+\sum_{i=1}^kr\\ &=T(r)+\sum_{i=1}^k(2i+r)^5+2\left(\frac{k(k+1)}2\right)+kr\\ &=T(r)+\sum_{i=1}^k(2i+r)^5+k(k+1+r)\;. \end{align*}$$

Now

$$\begin{align*} \sum_{i=1}^k(2i+r)^5&=\sum_{i=1}^k(32i^5+80i^4r+80i^3r^2+40i^2r^3+10ir^4+r^5)\\ &=32\sum_{i=1}^ki^5+80r\sum_{i=1}^ki^4+80r^2\sum_{i=1}^ki^3+40r^3\sum_{i=1}^ki^2+20r^4\sum_{i=1}^ki+kr^5\;. \end{align*}$$

One can find closed forms for all of these summations, but if you need only the order, all you need to know is that for each $m\ge 0$, $$\sum_{i=1}^ki^m$$ is a polynomial in $k$ of degree $m+1$.

Thus, $T(n)$ is a sixth-degree polynomial in $k=\frac12(n-r)$ and therefore also a sixth degree polynomial in $n$: $T(n)$ is $\Theta(n^6)$.

share|improve this answer
    
Thank you very much @Brian -- very useful and easy to follow. Honestly, thank you! –  canton May 11 '12 at 10:52
add comment

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.