0
$\begingroup$

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

This is what the professor wrote me when I asked him for help.. Why assign problems that you haven't reviewed in class? Please can anyone help?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)

$\endgroup$
  • $\begingroup$ I suggest you actually read the textbook. $\endgroup$ – Will Jagy Nov 5 '13 at 19:36
  • $\begingroup$ 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 $\endgroup$ – Rich Sanchez Nov 5 '13 at 23:45
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ You are the man! $\endgroup$ – Rich Sanchez Nov 5 '13 at 23:44
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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}

$\endgroup$

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.