Transform recursive sequence to direct. I am taking the GRE General Exam in a few weeks and there are some problems about sequences that I have found a bit difficult, e.g given a sequence in recursive form like $S_{n} = S_{n-1} - 10$  and some value for this sequence $S_{3}=0$ what is the value  $S_{25}$?
I know that the sequence in the direct form is $S_{n} = -10n + 30 $ but how this turns out?
for example can someone tell me step by step whats $S_{n} = 2S_{n-1}-4$ direct formula given that $S_{1}=6$
Thanks
 A: First part:
$$S_n-S_{n-1}=-10$$
Summing by telescoping for $n=m$ down to $4$ gives
$$S_m-S_3=-10(m-3)\\
S_m=-10m+30 \Longleftrightarrow S_n=-10n+30\;\;\blacksquare$$
Second part:
$$\begin{align}
S_n&=2S_{n-1}-4\\
S_n-4&=2(S_{n-1}-4)\\
&=2^2 (S_{n-2}-4)\\
&=\vdots\\
&=2^{n-1}(S_1-4)\\
&=2^{n-1}(2)\\
&=2^n\\
S_n&=2^n+4\;\;\blacksquare
\end{align}$$
A: This is easy - given a recursively defined sequence $S_n$ you:
(1) transform it to a form s.t. there are no "exceptions" assuming that $S_n$ is zero for negative $n$. E.g. if $S_n=2S_{n-1} - 4$ and $S_1=6$, the equation $S_n=2S_{n-1} - 4$ (assuming that $S_{-1}$=0) would output $S_0=2*0-4=-4$, so we have to add +4*[n=0] and for the same reason for $S_1$ we have to add + 10 *[n=1] (where [blabla(n)] is a characteristic function of blabla - equal 1 if blabla(n), and 0 otherwise).
So:
$S_n=2S_{n-1} - 4 + 10*[n=1] +4*[n=0]$
(2) Now you define a function $S(x) = S_0x^0 + S_1x^1 + S_2x^2+... = \sum_0^{\infty} S_nx^n$
On the other hand, due to our recursive equation:
$S(x) = \sum_{n=0}^{\infty} S_nx^n =\\
\sum_{n=0}^{\infty} (2S_{n-1} - 4 + 10*[n=1] + 4*[n=0])x^n =\\
\sum_{n=0}^{\infty} (2S_{n-1} - 4)x^n + 10x +4 =\\
2\sum_{n=0}^{\infty} S_{n-1}x^n - 4 \sum_n^{\infty} x^n +10x +4=\\
2x\sum_{n=0}^{\infty}S_{n-1}x^{n-1} - 4 (\frac{1}{1-x}) +10x +4=\\
2x\sum_{n=0}^{\infty}S_{n}x^{n} + \frac{4}{x-1} + 10x +4=\\
2x S(x) +\frac{10x^2 - 6x}{x-1}$
So:
$S(x) = \frac{10x^2-6x}{(1-2x)(x-1)} = \frac{1}{1-2x} + \frac{4}{1-x} -5$
(3) So now we may expand it back to a series:
$S(x) = \sum_{n=0}^{\infty}(2x)^n + 4\sum_{n=0}^{\infty}x^n -5 =\\
\sum_{n=0}^{\infty} (2^n +4)x^n -5$
And as we defined $S(x)$ to be $\sum_{n=0}^{\infty} S_nx^n$ we may conclude that $S_n = 2^n+4 -5[n=0]$.
Checking for $n=0$: 1+4-5=0 ok, for $n=1$: 2+4=6 ok, for $n=2$ 4+4=8 ok!... :)
This method is pretty universal.
