finding a closed form for $a_0=0,a_{n} =a_{n-1}+n^2$

Question

can someone please help me wrap my head around and show me how to do this, my professor gave this to us in class to study before he starts the lesson over it next week and i cannot find an example similar to this in my textbook. I am trying hard to stay ahead in this class I just cannot figure this out.

Find a closed form for the following recurrences using either $guess-and-verify$ or $plug-and-chug$:

$a_n$ defined as follows:

$a_0=0$

$a_n=a_{n-1}+n^2$ (for $n\ge1$)

Thank you for any and all help, it is greatly appreciated.

Answer 1

More generally, a linear recurrence of the form $a_n = \alpha_1 a_{n-1}+\alpha_2 a_{n-2}+\dots+\alpha_ka_{n-k}+f(n)$ can be solved for a closed form solution.

First find the roots of the characteristic polynomial $\chi(x)=x^k-\alpha_1 x^{k-1}-\alpha_2 x^{k-2}-\dots-\alpha_{k-1}x^1-\alpha_k$

With roots $\lambda_1,\lambda_2,\dots,\lambda_k$ we have the general solution of the form $c_1\lambda_1^n+c_2\lambda_2^2+\dots+c_k\lambda_k^n$ with the following caveat: that any time a term is repeated, multiply it by an additional factor of $n$. For example, with roots $3,3,3,5,7,7$ we would have closed form $c_13^n+c_2n3^n+c_3n^23^n+c_45^n+c_57^n+c_6n7^n$

From there, compare the roots to the non-homogeneous piece $f(n)$. If any terms overlap here again, multiply by additional factors of $n$ as before. Add these to the general solution along with unknown constants multiplied to each piece. Note that polynomials are special cases corresponding to terms of the form $1^n$ (the $1^n$ is just invisible).

Next, solve for the unknowns for the particular part, and then solve for the unknowns of the general part based on initial conditions by plugging into the recurrence.

---

For your specific example:

$a_n=a_{n-1}+n^2 \implies \chi(x)=x-1$ which has just the root $\lambda=1$

The non-homogeneous part is $n^2$ which is a second degree polynomial, so we would hope for a general second degree polynomial to be the particular part, however since the root of the characteristic polynomial is $1$ and polynomials are a special case of polynomials times terms of the form $1^n$, we must multiply again by $n$. So, we have our particular solution should be an arbitrary degree three polynomial: $d_0+d_1n+d_2n^2+d_3n^3$

Solving for constants by plugging into recurrence:

$a_n=a_{n-1}+n^2\implies (d_0+d_1n+d_2n^2+d_3n^3)=(d_0+d_1(n-1)+d_2(n-1)^2+d_3(n-1)^3)+n^2$

$d_1n+d_2n^2+d_3n^3=d_1n-d_1+d_2n^2-2d_2n+d_2+d_3n^3-3d_3n^2+3d_3n-d_3+n^2$

$d_1-d_2+d_3+2d_2n-3d_3n+3d_3n^2=n^2$

implying $\begin{cases}d_0=\text{anything, so redundant to include}\\d_1=\frac{1}{6}\\ d_2=\frac{1}{2}\\ d_3=\frac{1}{3}\end{cases}$

Our equation then is of the form $a_n = c_1 1^n +\frac{1}{6}n+\frac{1}{2}n^2+\frac{1}{3}n^3=c_1+\frac{1}{6}n+\frac{1}{2}n^2+\frac{1}{3}n^3$

Using our initial condition that $a_0=0$ we find that $c_1=0$ giving the final solution of:

$$a_n = \frac{1}{6}n+\frac{1}{2}n^2+\frac{1}{3}n^3=\frac{n(1+3n+2n^2)}{6}=\frac{n(n+1)(2n+1)}{6}$$

Answer 2

hint

You are given \begin{align*} a_1 & = a_0+1^2\\ a_2 & = a_1+2^2\\ a_3 & = a_2+3^2\\ \vdots & = \vdots\\ a_n & = a_{n-1}+n^2 \end{align*} Now add these equations to get $$a_n = a_0+\sum_{k=1}^{n}k^2$$

Answer 3

Here's a good way to make a guess notice we have,

$$n^2=a_{n+1}-a_{n}=\frac{a_{n+1}-a_{n}}{(n+1)-n}$$

Notice that this is roughly $\approx$ the derivative of $a_n$ if we let it exist. So to roughly get $a_n$ we take the antiderivative, the integral. But the antiderivative of a 2nd degree polynomial is a third degree polynomial. So guess $a_n=ax^3+bx^2+cx+d$ ,plug it into your recursive equation and, equate coefficients.