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

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.

  • $\begingroup$ 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.) $\endgroup$ Aug 2 at 1:33

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.