Transform recursive sequence to direct.

Question

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

Answer 1

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

Answer 2

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.