Solving the following recurrence equation $T(n) = T(n-2)+n^2$, having $T(0)=1$, $T(1)=5 $

Question

Solve the following recurrence equation: $T(n) = T(n-2)+n^2$, having $T(0)=1$, $T(1)=5$.

I need to solve this equation but when I get to the particular solution with $n^2$ some of the terms I need cancel out and it's kind of impossible to find the constants at that point.

Here is the way I'm doing it, using $an^2+bn+c$ to replace $T(n)$; $$\begin{split} 0&=an^2+bn+c - a(n-2)^2-b(n-2)-c-n^2\\ &=an^2+bn- a(n-2)^2-b(n-2)+n^2\\ &=an^2+bn- a(n^2-4n+4)-b(n-2)-n^2\\ &=an^2+bn- an^2+4an-4a-bn-2b-n^2\\ &=4an-4a-2b-n^2\\ &=n(4a-n)+(-4a+2b)\\ \end{split}$$ But beyond that, I cannot find any way to find the constants.

Answer 1

You need to solve for even and odd separately, but first let's find the value of the sum of squares of all nonnegative integers from $0$ to $m$, a quantity we denote by $S(m)$ and which we will need later.

We make an assumption that $m\to S(m)$ is a polynomial of degree $3$ (which I won't justify here, and you can prove the formula by induction after we find it). Observing that $S(0)=0$, we have $S(m) = c_3 m^3 + c_2 m^2+ c_1 m$. Since $S(1)=1,S(2)=5$ and $S(3)=14$, we also have
\begin{align*} c_3+c_2+c_1 &= 1\\ 8*c_3+4*c_2+2*c_1 &= 5\\ 27*c_3+9*c_2+3*c_1 &= 14\end{align*}
The solution to this system of equations is $c_3=\frac 16, c_2=\frac 12, c_1=\frac13$. That is

$$S(m) = \frac{m^3+3m^2+2m}{6}= \frac{m(m+1)(m+2)}{6}.$$

Now to the problem:

$$T(2)-T(0)=2^2, T(4)-T(2)=4^2,\dots,T(2m)-T(2m-2)= (2m)^2.$$ Adding up,

$$T(2m)-T(0)= \underset{\mbox{even}}{\underbrace{2^2+ \dots + (2m)^2}}= 2^2(1^2+\dots+m^2) = 4S(m).$$

That is $$T(2m)= T(0)+ \frac{2m(m+1)(m+2)}{3}.$$

Similarly $$T(3)-T(1)=3^2,\dots, T(2m+1)-T(2m-1)=(2m+1)^2,$$

Therefore

$$T(2m+1)-T(1) = \underset{\mbox{odd}}{\underbrace{3^2+5^2+ \dots + (2m+1)^2}} = S(2m+1) - 1^2- (2^2+\dots + (2m)^2)=S(2m+1)-1 - 4S(m).$$

I'll leave simplifying this last expression to you.

Answer 2

Since $n^2=2\binom{n}{2}+\binom{n}{1}$, it follows from the hockey-stick identity that $$ \begin{split} \sum_{k=0}^{n}{k^2}&=2\binom{n+1}{3}+\binom{n+1}{2}=\frac{(n+1)n(n-1)}{3}+\frac{(n+1)n}{2}\\ &=\frac{(n+1)n}{6}(2(n-1)+3)=\frac{n(n+1)(2n+1)}{6}. \end{split} $$ This identity lets us find the values $T(n)$ separately for even $n$ and for odd $n$.

For even $n$: $$ \begin{split} T(2n)&=T(0)+\sum_{k=1}^{n}(2k)^2=1+4\sum_{k=1}^{n}k^2=1+\frac{4n(n+1)(2n+1)}{6}\\ &=\frac{4n^3+6n^2+2n+3}{3}=\frac{(2n+3)(2n^2+1)}{3}. \end{split} $$ For odd $n$: $$ \begin{split} T(2n+1)&=T(1)+\sum_{k=1}^{n}(2k+1)^2=5+\sum_{k=1}^{2n+1}k^2-1^2-\sum_{k=1}^{n}(2k)^2=\\ &=4+\frac{(2n+1)(2n+2)(4n+3)}{6}-\frac{4n(n+1)(2n+1)}{6}=\\ &=4+\frac{(2n+1)(n+1)}{3}((4n+3)-2n)=4+\frac{(n+1)(2n+1)(2n+3)}{3}\\ &=\frac{4n^3+12n^2+11n+15}{3}=\frac{(2n+5)(2n^2+n+3)}{3}. \end{split} $$