How to solve recurrence relation $u_0=0, u_{n+1}=u_n+2n+1$

Question

I know the explicit form for $u_0=0, u_{n+1}=u_n+2n+1$ is $u_n=n^2$ but I want to know if there is a generalized or formal way of finding the explicit term for this kind of sequences.

The answer seems to be some kind of “guessing” followed by an induction proof to validate the choice of the explicit formula, but there is no easy way to do so (apart from arithmetic-geometric sequences).

Note: WolframAlpha seems to solve them, I wonder how it does.

Answer 1

In general, given initial condition $u_0$ to the recurrence $$u_{n+1}=u_n+a_n$$ with $a_n$ being an arbitrary sequence, we see that $$u_{k+1}-u_k=a_k$$ so that $$\sum_{k=0}^{n}(u_{k+1}-u_{k})=u_{n+1}-u_0$$ is the same as $\sum_{k=0}^{n}a_k,$ thus $$u_n=u_0+\sum_{k=0}^{n-1}a_k.$$ Use $u_0=0$ and $a_k=2k+1$ so that $$\begin{align} u_n&=0+\sum_{k=0}^{n-1}(2k+1)\\ &=2\sum_{k=0}^{n-1}k+\sum_{k=0}^{n-1}(1)\\ &=2\cdot\frac{n(n-1)}{2}+n\\ &=n^2. \end{align}$$

Answer 2

Telescoping to \begin{align*} \sum_{k=1}^{n}(u_{k+1}-u_{k})=\sum_{k=1}^{n}(2k+1). \end{align*}

Answer 3

Another way:

Let $U_n=An^2+Bn+C$, then $$A(n+1)^2+B(n+1)+C-(An^2+Bn+C)=2n+1 \implies An^2+2An+A+Bn+B+C-An^2-Bn-C=2n+1,$$ We get $2An+A+B=2n+1 \implies A=1, B=0$. Then $U_n=n^2+C$, using $U_0=0$, we get $U_n=n^2$.

Answer 4

Generating functions. Having $f(x)=\sum_{n\geq 0}u_nx^n=\sum_{n\geq 1}u_{n-1}x^n+2\sum_{n\geq 1}nx^n-\sum_{n\geq 1}x^n$, then we can see that $f(x)=xf(x)+2x/(1-x)^2-1/(1-x)$, or after some algebra $f(x)=x(x+1)/(1-x)^3$. Now using for example partial fractions decomposition we can find out $$ u_n=[x^n]f(x)=[x^n]\left(\frac{1}{1-x}-\frac{3}{(1-x)^2}+\frac{2}{(1-x)^3}\right)\\=1-3(n+1)+2(n+1)(n+2)/2=n^2. $$ To figure out sums such as $\sum nx^n$, notice that $$\sum_{n\geq 1}nx^n=x\sum_{n\geq 1}nx^{n-1}=x\sum_{n\geq 1}(x^n)'=x(1/(1-x))'=x/(1-x)^2,$$ and similarly the other way for $1/(1-x)^2$ and $1/(1-x)^3$.

Anyway in my opinion, in this case it seems easier to just guess the solution and then prove it (for example by induction), or methods shown in other answers (such as telescoping).