# Recurrence relations problem

Don't understand why someone would assign problems that he hasn't reviewed... It's crazy... I ask for help and got that response lol If $S_{n+2} = 2S_{n+1} - S_n + 3$, what are the correct steps in finding the general solution, and the particular solution if $S_0 = 1$ and $S_1 = 5$?

So far though I'm probably wrong, I tried to make it into a $x^2 - 2x +1$, with $3/2$ and the particular solution. So that would give me characteristic roots of $1$. I believe the general equation is in the form of $S_n = A(r)^n + B(r)^n$ and I add the $3/2$ after.

I'm so confused. What am I doing wrong and what should I be doing to correct myself? Thank you all. (Keep in mind my math background is weak and limited so please try to keep it simple LOL)

• I suggest you actually read the textbook. – Will Jagy Nov 5 '13 at 19:36
• I did. Don't comprehend all and only got to that far in what i did. Brian said i was on right track tho... It's just difficult cause i dont understand all of the symbols since he didn't go over it... Thanks tho – Rich Sanchez Nov 5 '13 at 23:45

It looks to me as if you’ve done quite a bit right, but you’ve also gone astray in solving the homogeneous part of the recurrence.

The general solution to the homogeneous recurrence $S_{n+2}=2S_{n+1}-S_n$ is indeed to be obtained from the characteristic equation $x^2-2x+1=0$, which does have a double root at $x=1$. However, a double root like this is treated differently from a pair of distinct roots.

If we’d found distinct roots $r_1$ and $r_2$, the general solution would have been $S_n=Ar_1^n+Br_2^n$, but when you have a double root $r$, $S_n$ isn’t given by $Ar^n+Br^n$: that’s really just $(A+B)r^n$, or $Cr^n$ for some constant $C$, and you still need a second solution. The correct general solution in this case is $S_n=Ar^n+Bnr^n$.

In your problem $r=1$, and $1^n=1$ for all $n$, so the general solution of the homogeneous recurrence is $S_n=A+Bn$. Now you have to deal with the non-homogeneous part of the recurrence, the $+3$, by finding a particular solution. The non-homogeneous part if of the form $p(n)s^n$ for some polynomial $p$ and constant $s$: $p(n)$ is the constant polynomial $3$, and $s=1$. If $s$ were not a root of the characteristic equation, we’d expect a particular solution of the form $q(n)s^n$ for some polynomial $q$ of degree at most that of $p$, which in this case means that $q$ would simply be a constant. Because $1$ is a double root of the characteristic equation, however, we have to multiply that by $n^2$. Thus, we expect a particular solution of the form $S_n=cn^2$ for some constant $c$.

To determine $c$, plug the formula $S_n=cn^2$ into the recurrence and solve for $c$: $S_{n+2}=2S_{n+1}-S_n+3$ becomes

$$c(n+2)^2=2c(n+1)^2-cn^2+3\;,$$

which expands to $$cn^2+4cn+4c=2cn^2+4cn+2c-cn^2+3\;.$$

Simplifying this, we get $2c=3$, or $c=\frac32$. The general solution to the non-homogeneous recurrence is therefore

$$S_n=A+Bn+\frac32n^2\;.\tag{1}$$

The values of $A$ and $B$ will be determined from the initial values $S_0=1$ and $S_1=5$. Just substitute $n=0$ and $n=1$ into $(1)$, together with the known values of $S_0$ and $S_1$, to get the system

\left\{\begin{align*} 1&=A\\ 5&=A+B+\frac32\;, \end{align*}\right.

which is very easily solved for $A$ and $B$.

• You are the man! – Rich Sanchez Nov 5 '13 at 23:44

Without considering the general way to get explicit expression of this kind recurrence, the relation you provide could be written as $S_{n+2}- S_{n+1} = S_{n+1} - S_{n} + 3$.

So if we define $a_n = S_{n+1} - S_n$, we get $a_{n+1} = a_{n} + 3$ and $a_0 = S_1 -S_0 =4$. Then we get easily $a_n = 3n + 4$. Finally the value of $S_n$ is found as $(\sum_{i=0}^{n-1} a_i) + S_0$

Define $F(z) = \sum_{n \ge 0} S_n z^n$, multiply your recurrence by $z^n$, sum over $n \ge 0$ and recognize: \begin{align} \sum_{n \ge 0} 3 z^n &= \frac{3}{1 - z} \\ \sum_{n \ge 0} S_{n + 1} z^n &= \frac{F(z) - S_0}{z} \\ \sum_{n \ge 0} S_{n + 2} z^n &= \frac{F(z) - S_0 - S_1 z}{z^2} \end{align} to get: $$\frac{F(z) - 1 - 5 z}{z^2} = 2 \frac{F(z) - 1}{z} - F(z) + \frac{3}{1 - z}$$ Solving this for $F(z)$ returns: $$F(z) = \frac{1 + 2 z}{(1 - z)^3} = \frac{3}{(1 - z)^3} - \frac{2}{(1 - z)^2}$$ Both terms can be expanded by the (generalized) binomial theorem: \begin{align} S_n &= 3 (-1)^n \binom{-3}{n} - 2 (-1)^n \binom{-2}{n} \\ &= 3 \binom{n + 2}{2} - 2 \binom{n + 1}{1} \\ &= 3 \frac{(n + 2) (n + 1)}{2} - 2 \frac{n + 1}{1} \\ &= \frac{3 n^2 + 5 n + 2}{2} \end{align}