4
$\begingroup$

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.

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

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

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

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

$\endgroup$
  • $\begingroup$ For $n=1$, $U_n=\frac{3}{2}$, but $R_n=-3$. $\endgroup$ – Fatos Morina Apr 25 '15 at 10:50
  • $\begingroup$ @Phatossi It seems I made a mistake, I used $n^2+1$ instead of $n^2+2n+1$. It should be good, now. $\endgroup$ – Kitegi Apr 25 '15 at 17:18
  • $\begingroup$ 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. $\endgroup$ – DanielV Apr 25 '15 at 23:50
  • $\begingroup$ @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? $\endgroup$ – Kitegi Apr 25 '15 at 23:54
  • $\begingroup$ @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. $\endgroup$ – DanielV Apr 26 '15 at 0:09
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.