unfolding of a recurrence

1k Views Asked by At

I've been reading the book "Concrete Mathematics" from Graham et. al. And there is a relation (on pg. 27) $s_n = s_{n-1}a_{n-1}/b_n$, and authors point that this relation can be unfolded, resulting with

$$s_n = \frac{a_{n-1} \ldots a_1}{b_n \ldots b_2}$$

I don't understand why authors stops unfolding at n = 2 ?

Shouldn't it be $$s_n = \frac{a_{n-1} \ldots a_0}{b_n \ldots b_1}$$

Thanks in advance

1

There are 1 best solutions below

5
On BEST ANSWER

Look back up the page to equation $(2.9)$,

$$a_nT_n=b_nT_{n-1}+c_n\;.$$

Since the numbers $T_n$ are indexed starting at $n=0$, $(2.9)$ makes sense only for $n\ge 1$. In particular, $a_n,b_n$, and $c_n$ are defined only for $n\ge 1$. There is no problem with

$$s_n = \frac{a_{n-1} \ldots a_1}{b_n \ldots b_2}\;,$$

since the smallest subscript appearing on either $a$ or $b$ is $1$, but extending the unfolding one more step to

$$s_n = \frac{a_{n-1} \ldots a_0}{b_n \ldots b_1}$$

would require us to have $a_0$, and we don’t, because we don’t have a $T_{-1}$.