Convert recurrent formula with polynomial term / parameter to explicit formula

Question

So, I know how to convert to explicit formulas things like the Fibonacci sequence cause it only consists of $a_n$ like this:

$$a_{n} = a_{n-1} + a_{n-2}$$

However my problem is I've encountered a type of this problem I haven't been thought how to approach, and can't find the solution anywhere:

$$a_{n} = a_{n-1} + n+1$$

The sequence this is supposed to represent is: $0, 2, 5, 9, 14, 20, 27 ...$

The correct explicit formula that I don't know how to get to for this is:

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

---

To solve this, I've tried converting it to:

$$r^n = r^{n-1} + n + 1$$

and treating n as the superscript of r... to end up with

$$r^2=r+2+1$$

..which is the standard procedure I've been taught, then solving for $r$ to get $r_1$ and $r_2$ and adding $\alpha$ and $\beta$ like I've been taught to get:

$$a_n = \alpha(r_1)^n + \beta(r_2)^n$$

.. then plugging in known $n$ and $a_n$ values to get a system of equations and then finally plug in the resulting $\alpha$ and $\beta$ to get the explicit formula, which however turned out to be complete gibberish. I'm sure I didn't mess up the system of equations or any step since I used automated equation solving to make sure.

That means the problem is me not knowing how to deal with that problem in the first place, I think. It seems to have a non-standard procedure to it.

Answer 1

The formula which you give, $a_n=\frac{n}{2}(n+3)$ is not the correct formula for the sequence defined recursively by $a_1=0, a_{n+1}=a_n+n+1$.

This is a sequence with a constant second difference.

The sequence is

$$ 0, 2, 5, 9, 14, 20, 27,\cdots $$

The first difference is found by subtracting each term from the following term:

$$ 2, 3, 4, 5, 6, 7, \cdots $$

The second difference is a constant sequence consisting entirely of ones.

When the second difference is constant, $a_n$ is a second degree polynomial in $n$

$$a_n=rn^2+sn+t$$

We are given that

$$ a_{n+1}-a_n=n+1 $$

Therefore

\begin{eqnarray} r(n+1)^2+s(n+1)+t-(rn^2+sn+t)&=&n+1\\ 2rn+r+s&=&n+1 \end{eqnarray}

So

\begin{eqnarray} 2r&=&1\\ r+s&=&1 \end{eqnarray}

which gives $r=s=\frac{1}{2}$

Now we have that

\begin{eqnarray} a_n&=&\frac{1}{2}n^2+\frac{1}{2}n+t\\ a_1&=&\frac{1}{2}+\frac{1}{2}+t=0\\ \end{eqnarray}

Therefore, $t=-1$

\begin{eqnarray} a_n&=&\frac{1}{2}n^2+\frac{1}{2}n-1\\ &=&\frac{1}{2}(n^2+n-2)\\ &=&\frac{1}{2}(n-1)(n+2) \end{eqnarray}

Answer 2

From the original recurrence relation $$a_n=a_{n-1}+n+1$$ $$=(a_{n-2}+n)+n+1$$ $$=((a_{n-3}+(n-1))+n)+n+1$$ Continuing this pattern and knowing that $a_1=0$, we then have that $$a_n=\sum_{r=2}^{n+1}r=\frac{1}{2}(n+1)(n+2)-1=\frac{1}{2}(n^2+3n+2)-1=\frac{1}{2}(n^2+3n)=\frac{n}{2}(n+3)$$

You can also approach this in the way you stated but we must first solve the associated homogeneous recurrence relation $$a_n=a_{n-1}$$ and then find the particular solution $$a_n=\lambda n+\mu$$ by using this definition for $a_n$ in the original recurrence relation.

Answer 3

If $g(x) = \sum_{n=0}^\infty a_n x^n$ is the generating function of your sequence (with $a_0 = 0$), you have $$ g(x) = \sum_{n=1}^\infty (a_{n-1} + n + 1) x^n = x g(x) + \sum_{n=1}^\infty (n+1) x^n = x g(x) + \frac{x(2-x)}{(1-x)^2}$$ so that $$g(x) = \frac{x (2-x)}{(1-x)^3}$$ Convert this to partial fractions: $$ g(x) = \frac{1}{(1-x)^3} - \frac{1}{1-x} $$ Note that $1/(1-x) = \sum_{n=0}^\infty x^n$ while $$ \frac{1}{(1-x)^3} = \frac{1}{2} \frac{d^2}{dx^2} \frac{1}{1-x} = \sum_{n=0}^\infty \frac{(n+1)(n+2)}{2} x^n $$