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$



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

  • $\begingroup$ for the second part I know that $S_{1}=6$, your solution don't accept this $\endgroup$
    – stratman
    Oct 25 '16 at 16:57
  • $\begingroup$ The solution works now. $\endgroup$ Oct 26 '16 at 0:50

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


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


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.