General and particular solution from recurrence equation

Question

I need to find the General Solution of

$S_n = 3S_{n-1}-10$ for n = 1,2,3,4....

then I need to find the particular solution where $S_0 = 15$, then check the particular solution with the original recurrence equation using $S_6$.

My question is how do I find the General Solution from the above recurrence equation. I know the GS is in the form of $S_n = A{r_1}^n + B{r_2}^n$, but the recurrence equation is already in $S_n$. So i'm a bit confused.

Answer 1

You’ve given the general form for the solution to a second-order recurrence; this is only a first-order recurrence. There are many ways to handle it; here’s one that works with any recurrence of the form $x_n=ax_{n-1}+b$.

Let $T_n=S_n+d$ for each $n$, where $d$ is some constant whose value is yet to be determined. Note that $S_n=T_n-d$ for each $n$, so the recurrence can be rewritten as

$$T_n-d=3(T_{n-1}-d)-10\;,$$

or

$$T_n=3T_{n-1}-2d-10\;.\tag{1}$$

If we now cleverly set $d=-5$, $(1)$ becomes the very simple recurrence $T_n=3T_{n-1}$, whose solution can be written down instantly:

$$T_n=3^nT_0\;.\tag{2}$$

Now by definition $T_n=S_n+d=S_n-5$, and $T_0=S_0+d=S_0-5$, so $(2)$ can be rewritten

$$S_n-5=3^n(S_0-5)\;,$$

or

$$S_n=3^nS_0-5\cdot3^n+5=3^nS_0-5(3^n-1)\;.$$

In particular, if $S_0=15$, then

$$S_n=15\cdot3^n-5\cdot3^n+5=10\cdot3^n+5\;.\tag{3}$$

As a quick sanity check we can calculate a few values using $(3)$ and compare them with those calculated from the original recurrence.

By the recurrence we have $S_0=15$, $S_1=3\cdot15-10=35$, and $S_2=3\cdot35-10=95$; by $(3)$ we have $S_0=10\cdot1+5=15$, $S_1=10\cdot3+5=35$, and $S_2=10\cdot9+5=95$.

Answer 2

The homogeneous recurrence equation is a $\mathbf 1$st order linear recurrence, hence the general solution has the form $S_0r^n$, and $r$ is the solution of the characteristic equation, which gives in the present case $$A\cdot3^n.$$

As for the inhomogeneous equation, a particular solution is a constant sequence, which is $5$ by identification. Add this particular solution to the general solution of the homogeneous equation: $$u_n=A\cdot 3^n+5$$ and determine the solution which satisfies the initial condition from this form.

Answer 3

Even without other tricks, it is possible to run the recurrence for a few times and see a pattern:

$$\begin{align*} S_n &= 3S_{n-1}-10\\ &= 3(3S_{n-2}-10)-10\\ &= 3^2S_{n-2}-3\cdot10-10\\ &= 3^2(3S_{n-3}-10)-3\cdot10-10\\ &= 3^3S_{n-3}-3^2\cdot10-3\cdot10-10\\ &\vdots\\ &= 3^kS_{n-k}-10\sum_{i=0}^{k-1}3^i\\ &= 3^kS_{n-k}-10\cdot\frac{3^k-1}{3-1}\\ &= 3^nS_0-5(3^n-1) \end{align*}$$ The last line is obtained by substituting $k=n$.