How to compute the formula of $S_n$

117 Views Asked by At

$S_1$=a, $S_2$=b, $S_n$=|$S_{n-1}$-$S_{n-2}$|(n $\ge$3). Can I compute the formula of $S_n$? Thanks in advance.

1

There are 1 best solutions below

2
On

If $b=qa+r$, then the sequence is

$a,b, (q-1)a+r, a, (q-2)a+r, (q-3)a+r, a, (q-4)a+r, (q-5)a+r, a, \dots$

eventually you get to two consecutive terms that are $a, r$ or $r,a$, and you repeat. Thus you basically get the sequence from Euclid's Algorithm. That is, the sequence eventually ends with

$gcd(a,b), gcd(a,b), 0,gcd(a,b), gcd(a,b), 0, \dots$