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