Sum of squares by treating it as a nonhomogenous recurrence

482 Views Asked by At

Let $T(n) = T(n-1) + n^2$ where $T(0) = 0$.

The homogenous part $T(n) = T(n-1)$ has characteristic polynomial $x - 1 = 0$ and root $1$, which means $T(n) = \alpha \cdot 1^n$ for the homogenous part.

I am not sure how to do the nonhomogenous part. I tried this:

$cn^2 = c(n-1)^2 + n^2$ but $c$ doesn't become a nice constant.

I am trying to ultimately derive $T(n) = n(n+1)(2n+1)/6$

1

There are 1 best solutions below

0
On

You should try with a full cubic, not just the highest degree term. So you have to try $T(n) = \alpha n^3 + \beta n^2 + \gamma n + \delta$. Setting $T(0)=0$ we have $\delta=0$.
Then, setting $T(n) = T(n-1) + n^2$ yields: $$\begin{cases} -3\alpha -1 = 0 \\ 3\alpha - 2\beta = 0 \\ -\alpha + \beta - \gamma = 0\end{cases}$$ Solving this, gives you the result: $\alpha = 1/3$, $\beta = 1/2$, $\gamma = 1/6$.