# Solve the recurrence of the alternating sum $R_n=R_{n-1}+(-1)^{n}(n+1)^{2}$

I have been trying to solve this recurrence for a few hours, but I haven't been able to find the solution yet:

$R_0=1$

$R_n=R_{n-1}+(-1)^{n}*(n+1)^{2}$.

I have been trying to substitute $T_n=(-1)^{n}*R_n$ and then solving for $T_n$ and got the sum:

$1+3+...+\frac{n(n+1)}{2}$

but this sum $(-1)^{n}\frac{n(n+1)(n+2)}{6}$ didn't give the generalized form that would give the terms of the recurrence.

Additionally, I have been trying to substitute $n=2*a$:

$\sum_{k=1}^a (-1)^{2k}*(2k+1)^{2}+ \sum_{k=1}^a (-1)^{2k-1}*(2k)^2$

and I got $\frac{n*(n+3)}{2}$, but it doesn't seem to be right either.

Edited: I have added the initial values.

• no initial values? – abel Apr 25 '15 at 10:03
• Just added the initial value. – Fatos Morina Apr 25 '15 at 10:40
• May be, consider the case of $R_{2n}$ and $R_{2n+1}$ separately. – Claude Leibovici Apr 25 '15 at 13:15

\begin{align} R_n-R_{n-1}&=(-1)^n(n+1)^2;\qquad R_0=1\\ R_n-\underbrace{R_0}_{=1}&=\sum_{r=1}^{n}(-1)^r(r+1)^2\qquad\text{by telescoping}\\ R_n&=\sum_{r=0}^{n}(-1)^r(r+1)^2\\ &=\sum_{r=1}^{n+1}(-1)^{r-1}r^2\\ \end{align}

Note that $-r^2+(r+1)^2=r+(r+1)$.

Hence, for even $n$,

\begin{align} R_n&=1^2 \underbrace{-2^2+3^2}_{2+3} \underbrace{-4^2+5^2}_{4+5}+\cdots+\underbrace{-n^2+(n+1)^2}_{n+(n+1)}\\ &=1+2+3+4+\cdots+n+(n+1)\\ &=\frac{(n+2)(n+1)}2=\binom {n+2}2 \end{align}

and for odd $n$,

\begin{align} R_n&= \underbrace{1^2-2^2}_{-1-2}+ \underbrace{3^2-4^2}_{-3-4}+\cdots+\underbrace{n^2-(n+1)^2}_{-n-(n+1)}\\ &=-(1+2+3+4+\cdots+n+(n+1))\\ &=-\frac{(n+2)(n+1)}2=-\binom {n+2}2 \end{align}

Hence the general solution is $$R_n=(-1)^n\frac {(n+2)(n+1)}2=(-1)^n \binom {n+2}2\qquad\blacksquare$$

• Thank you very much. I really appreciate your help. – Fatos Morina Apr 26 '15 at 6:15
• You're most welcome! – hypergeometric Apr 26 '15 at 6:23

We have $$R_n-R_{n-1}=(-1)^n (n+1)^2=(-1)^n(n^2+2n+1)$$ It's the first time a see a recurrence relation like that, so I'm gonna try something that looks like the second term. Maybe $U_n=(-1)^n (an^2+bn+c)$

Then \begin{align} U_n-U_{n-1}&=(-1)^n (an^2+bn+c + a(n-1)^2 +b(n-1)+c)\\ &= (-1)^n((2a)n^2+(2b-2a)n+(2c-b+a)) \end{align}

To get a solution we need to have: $$2a=1;\ 2b-2a=2;\ 2c-b+a=1$$ $$a=1/2;\ b=3/2;\ c=1$$

So $$U_n=(-1)^n(n^2+3n+2)/2$$ satisfies the recurrence relation. And now we have: $$R_n-U_n=R_{n-1}-U_{n-1}$$

So $R_n=U_n+k$ where $k$ is some constant.

Since $R_0=U_0=1$, then: $$R_n= U_n= (-1)^n(n^2+3n+2)/2$$

• For $n=1$, $U_n=\frac{3}{2}$, but $R_n=-3$. – Fatos Morina Apr 25 '15 at 10:50
• @Phatossi It seems I made a mistake, I used $n^2+1$ instead of $n^2+2n+1$. It should be good, now. – Kitegi Apr 25 '15 at 17:18
• This approach only works because the problem was contrived to make it work. The general term for $U_n$ is going to be something like $A^n~n^2 + B^n~n + C^n + D^n + \dots$, and it is in fact only a coincidence of the construction of this problem that the only exponential growth involved is $(\pm 1)^n$. This problem was in some sense made to be misleading like that. – DanielV Apr 25 '15 at 23:50
• @DanielV I think the approach only needs to be modified slightly for similar problems. Could you give me an example where this doesn't work? – Kitegi Apr 25 '15 at 23:54
• @Farnight Look at the first matrix in my solution and the linear equation just before it. That matrix has eigenvalues of $\pm 1$ which is why the telescoping and solution guessing works. But by changing a few constants around, those eigenvalues really could be anywhere. Telescoping only works when all the eigenvalues of the matrix are $1$, and having $-1$ is just a coincidence. If the expression had been $R_n = \pi~R_{n-1} + \text{stuff}$ ... , then we wouldn't be able to rely on the kindness of the question maker. – DanielV Apr 26 '15 at 0:09

$$R_n=R_{n-1}+(-1)^{n}(n+1)^{2}$$

A general technique for solving this kind of recursion is to expand $R_n$, $R_{n+1}$, $R_{n+2}$, $\dots$, and solve the resulting system of linear equations of non linear variables.

$$\begin{array} {ccccccccc} % R_{n} & = & R_{n-1} & + & (-1)^nn^2 & + & 2~(-1)^nn & + & (-1)^n \\ % R_{n+1} & = & R_{n} & - & (-1)^nn^2 & - & 4~(-1)^nn & - & 4~(-1)^n \\ % R_{n+2} & = & R_{n+1} & + & (-1)^nn^2 & + & 6~(-1)^nn & + & 9~(-1)^n \\ % R_{n+3} & = & R_{n+2} & - & (-1)^nn^2 & - & 8~(-1)^nn & - & 16~(-1)^n \\ % \end{array}$$

Now we wish to eliminate $x = (-1)^nn^2$, $y=(-1)^nn$ and $z=(-1)^n$ using introductory linear algebra:

$$\begin{array} {ccccccccc} % R_{n} & = & R_{n-1} & + & x & + & 2~y & + & z \\ % R_{n+1} & = & R_{n} & - & x & - & 4~y & - & 4~z \\ % R_{n+2} & = & R_{n+1} & + & x & + & 6~y & + & 9~z \\ % R_{n+3} & = & R_{n+2} & - & x & - & 8~y & - & 16~z \\ % \end{array}$$

Eliminate $x,y,z$ to get:

$$R_{n+3} = -2~R_{n+2} + 2~R_{n} + R_{n-1}$$

Which can be solved using any of the tapestry of techniques for solving linear recurrences, I prefer matrices:

$$\begin{bmatrix} R_{n+3} \\ R_{n+2} \\ R_{n+1} \\ R_{n+0} \end{bmatrix} = \begin{bmatrix} -2 & 0 & 2 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}^n \begin{bmatrix} R_{3} \\ R_{2} \\ R_{1} \\ R_{0} \end{bmatrix}$$

Jordan Normal Form, etc, to get:

$$% \begin{bmatrix} R_{n+3} \\ R_{n+2} \\ R_{n+1} \\ R_{n+0} \end{bmatrix} = % \begin{bmatrix} 1 & 1 & -2 & 1 \\ 1 & -1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & -1 & -1 & -1 \end{bmatrix} % \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & -1 \end{bmatrix}^n % \begin{bmatrix} 1 & 1 & -2 & 1 \\ 1 & -1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & -1 & -1 & -1 \end{bmatrix}^{-1} % \begin{bmatrix} R_{3} \\ R_{2} \\ R_{1} \\ R_{0} \end{bmatrix} %$$

$$= % \frac{1}{8} \begin{bmatrix} 1 & 1 & -2 & 1 \\ 1 & -1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & -1 & -1 & -1 \end{bmatrix} % \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & (-1)^n & (-1)^{n-1}~{n \choose 1} & (-1)^{n-2}~{n \choose 2} \\ 0 & 0 & (-1)^n & (-1)^{n-1}~{n \choose 1} \\ 0 & 0 & 0 & (-1)^n \end{bmatrix} % \begin{bmatrix} 1 & 3 & 3 & 1 \\ -1 & -3 & 5 & -1 \\ -2 & 2 & 2 & -2 \\ 4 & 4 & -4 & -4 \end{bmatrix} % \begin{bmatrix} R_{3} \\ R_{2} \\ R_{1} \\ R_{0} \end{bmatrix} \\ %$$

And adding initial conditions and expanding:

$$R_{n} = \frac{(-1)^n}{2} \left(n^2 + 3n + 2\right)$$

@hypergeometric's solution is my favorite, but another (very general) way of solving this recurrence is by a so-called generating function. Let us define $f(x) = \sum_{n=0}^\infty R_n x^n$. Then, $$R_n = R_{n-1} + (-1)^n(n+1)^2 \implies R_nx^n = x R_{n-1} x^{n-1} + (-1)^n (n+1)^2 x^n$$ Summing both sides from $n=1$ to $\infty$, we obtain $$f(x)-1 = xf(x) + \sum_{n=1}^\infty (-1)^n (n+1)^2 x^n$$ We can now evaluate the remaining sum by noting $$\frac{d^2}{dx^2} \frac{1}{1-x} = \sum_{n=2}^\infty n(n-1)x^{n-2} = \sum_{n=0}^\infty (n+2)(n+1) x^n = \sum_{n=0}^\infty (n+1)^2 x^n + \sum_{n=0}^\infty (n+1)x^n$$ Thus (changing the limits of summation from $n=0$ to $n=1$), $$\frac{2}{(1-x)^3} - \frac{1}{(1-x)^2} - 1 = \sum_{n=1}^\infty (n+1)^2 x^n$$ This (substituting $-x$ for $x$) gives us $$(1-x)f(x) = \frac{2}{(1+x)^3} - \frac{1}{(1+x)^2} \implies f(x) = \frac{1}{(1+x)^3} = \sum_{n=0}^\infty \underbrace{\frac{(-1)^n}{2}(n+1)(n+2)}_{R_n}x^n.$$

The trick was that we found $f(x)$ in closed form, then re-expanded as a series, since it was of a well-known form. The coefficients of that series are, by construction, $R_n$.

• Thanks! That's very kind of you :) – hypergeometric Apr 26 '15 at 4:43