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

Question

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.

Please help me and if you can figure out, please tell me what I did wrong.

Edited: I have added the initial values.

Answer 1

$$\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$$

Answer 2

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$$

Answer 3

$$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)$$

Answer 4

@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$.