# Recurrence & Rate of Growth

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.

-
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

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)$.

-
Thank you very much @Brian -- very useful and easy to follow. Honestly, thank you! – canton May 11 '12 at 10:52