# Question about Graham, Knuth, and Patashnik's technique for turning first-order recurrences into summations

In Concrete Mathematics, Graham, Knuth, and Patashnik describe the following technique for turning first order recurrence relations of the form $$$$a_nT_n = b_nT_{n-1} + c_n$$$$

into summations.

• Step 1. Find a function $$s_n$$ with the property that $$s_nb_n = s_{n-1}a_{n-1}$$
• Step 2. Multiply both sides of the recurrence by $$s_n$$, giving you $$s_na_nT_n = s_nb_nT_{n-1} + s_nc_n$$ or equivalently, $$s_na_nT_n = s_{n-1}a_{n-1}T_{n-1} + s_nc_n$$
• Step 3 Define $$S_n = s_na_nT_n$$ and rewrite the recurrence as $$S_n = S_{n-1} + s_nc_n$$
• Step 4. Write $$S_n$$ as the sum $$S_n = s_0a_0T_0 + \sum_{k = 1}^n s_kc_k = s_1b_1T_0 + \sum_{k = 1}^n s_kc_k$$
• Step 5. Find a closed form for the summation $$S_n$$.
• Step 6. To find the closed form for $$T_n$$, simply multiply the closed form of $$S_n$$ by $$\frac{1}{s_na_n}$$.

Additionally, they claim that the appropriate value of $$s_n$$ is always given by $$s_n = \frac{a_1a_2\cdots a_{n-1}}{b_2b_3\cdots b_n}$$ which they justify by reasoning as follows:

Since $$b_ns_n = s_{n-1}a{n-1}$$, we know that $$s_n = \frac{s_{n-1}a_{n-1}}{b_n}$$ plugging in the value of $$s_{n-1}$$, we find that this is equal to $$\frac{s_{n-2}a_{n-2}a_{n-1}}{b_{n-1}b_n}$$ and by continuing in this fashion, we ultimately find that $$s_n = \frac{a_1a_2\cdots a_{n-1}}{b_2b_3\cdots b_n}$$ But when I continue in this fashion what I find is that $$s_n = \frac{s_1a_1a_2\cdots a_{n-1}}{b_2b_3\cdots b_n}$$ Notice the $$s_1$$ in the numerator. What am I doing wrong here?

$$s_1$$ isn't defined if we define $$s_n = \dfrac{a_1 a_2 ... a_{n-1}}{b_2 b_3 ... b_n}$$, because there is $$b_2$$ in the denominator where $$n=1$$. If you define $$s_1 = 1$$, the problem will be solved.
• In the eyes of Graham Knuth and Patashnik, $\frac{a_1 a_2 ... a_{n-1}}{b_2 b_3 ... b_n}$ would be shorthand for dividing $\prod_{1 \le i \le n-1} a_i$ by $\prod_{2 \le i \le n} b_i$. When $n=1$, both products are empty, so $s_1 = \frac11 = 1$. (Not that the value of $s_1$ matters much, provided it is nonzero.) Aug 2 at 1:33