Solving the recurrence $T(1) = 1$, $T(n) = T(n-1) + n^2$

Question

How do you solve the following recurrence?

• $T(1) = 1$

• $T(n) = T(n-1) + n^2$

Answer 1

First, let me mention that in the real world you can just plug this sum into a program like sage and it will compute it for you. For instance, see this wolframalpha computation, which immediately gives the answer

$$ \sum_{k=0}^{n-1} 3^k (n-k)^3 = \frac{1}{8} \Big ( 33 (3^n-1) - 4n^3 - 18n^2 -36n \Big ). $$

This is because your sum is hypergeometric (the ratio of consecutive terms is a quotient of polynomials), and there are "well known" algorithms which will always compute a closed form (or tell you that one doesn't exist!). See, for instance, the excellent book A=B by Petkovsek, Wilf, and Zeilberger for more about these algorithms.

This may feel flippant, but it's much faster (and less error prone) than trying to solve the sum by hand. In case you don't believe me...

---

You might ask how you could have solved this equation by hand, if push came to shove (for instance, on some kind of exam). Notice that your sum looks like some polynomial in $k$ times something exponential in $k$:

$$ \sum_k \underbrace{(n-k)^3}_{\text{polynomial in $k$}} \quad \underbrace{3^k}_{\text{exponential in $k$}} $$

As commenters are noting, there's a common trick for doing exactly this: Write your sum as a polynomial (or power series, if the sum is infinite) in $x$, then later evaluate at $x=3$ once we've simplified!

So for us, we want to look at the polynomial $\sum_{k=0}^{n-1} (n-k)^3 x^k$. We can simplify this using our knowledge of polynomials, then plug in $x=3$ at the end once it looks simpler!

Let's start by expanding our $(n-k)^3$ to get

$$ \sum_{k=0}^{n-1} (n^3 - 3 n^2 k + 3 n k^2 - k^3) x^k $$

This breaks up into a bunch of simpler pieces

$$ n^3 \left ( \sum_{k=0}^{n-1} x^k \right ) - 3 n^2 \left ( \sum_{k=0}^{n-1} k x^k \right ) + 3 n \left ( \sum_{k=0}^{n-1} k^2 x^k \right ) - \left ( \sum_{k=0}^{n-1} k^3 x^k \right ) $$

But these are things we know how to sum! They're all basically geometric series, and you can find tables with closed forms for all of these. However, we can also use another memorable trick to compute them. The idea (as commenters have also pointed out) is to look at derivatives of $\frac{x^n - 1}{x-1} = \sum_{k=0}^{n-1} x^k$.

This is another great reason to replace the concrete $3^k$ in our sum by the more general variables $x^k$. We have access to more techniques when working with polynomials (for instance, differentiation) than we do when working with concrete numbers!

Indeed, notice

$$ \frac{x^n - 1}{x-1} = \sum_{k=0}^{n-1} x^k $$

$$ \left ( \frac{x^n - 1}{x-1} \right )' = \left ( \sum_{k=0}^{n-1} x^k \right )' = \sum_{k=0}^{n-1} k x^{k-1} $$

$$ \left ( \frac{x^n - 1}{x-1} \right )'' = \left ( \sum_{k=0}^{n-1} x^k \right )'' = \sum_{k=0}^{n-1} k(k-1) x^{k-2} $$

$$ \left ( \frac{x^n - 1}{x-1} \right )''' = \left ( \sum_{k=0}^{n-1} x^k \right )''' = \sum_{k=0}^{n-1} k(k-1)(k-2) x^{k-2} $$

I'll leave you here with two exercises to finish off the problem!

First, can you write our sum

$$ n^3 \left ( \sum_{k=0}^{n-1} x^k \right ) - 3 n^2 \left ( \sum_{k=0}^{n-1} k x^k \right ) + 3 n \left ( \sum_{k=0}^{n-1} k^2 x^k \right ) - \left ( \sum_{k=0}^{n-1} k^3 x^k \right ) $$

As a linear combination of the derivatives above? After you've done this, can you actually compute the above derivatives and evaluate them at $x=3$ to get the answer?

Lastly, if you want to read more about techniques for solving these kinds of sums, I can't recommend Graham, Knuth, and Patashnik's Concrete Mathematics highly enough. You'll also find more of these "tricks" for manipulating sums as polynomials/power series in Wilf's excellent Generatingfunctionology.

---

I hope this helps ^_^