# Recurrence Relations - Method of Summation Factors

There is another way of solving recurrence relations of the form \(Aa_n = Ba_{n-1} + C\), where \(A\), \(B\) and \(C\) are functions of \(n\), which some references call the **method of summation factors**. This method is pretty straightforward when \(A\) and \(B\) are *linear* functions of \(n\), and it solves several recurrence relations problems in recreational mathematics and computer science, among others.

#### Contents

## Methodology

First, define a **summation factor** \(s_n\), which, when multiplied to the recurrence relation, gives

\[As_n a_n = Bs_n a_{n-1} + Cs_n.\]

This summation factor must be chosen such that the "new" sequence of numbers has an \((n - 1)^\text{th}\) term of \(Bs_n a_{n-1}\) and an \(n^\text{th}\) term of \(As_n a_n\). This factor is chosen to be

\[s_n = \frac{A_{n-1} A_{n-2} \ldots A_2 A_1}{B_n B_{n-1} \ldots B_3 B_2}.\]

Thus, we can now let \(b_n = As_n a_n\) and \(b_{n-1} = Bs_n a_{n-1}\). The recurrence relation now becomes

\[b_{n-1} = b_{n} + Cs_n,\]

where \(Cs_n\) can be thought of as the difference between the \((n - 1)^\text{th}\) and the \(n^\text{th}\) term. Thus, the closed form of \(b_n\) is

\[b_n = b_0 + \sum_{k = 1}^n Cs_k,\]

where \(C\) is a function of the index \(k\). But \(b_0 = A_{n = 0} s_0 a_0\) and \(b_n = As_n a_n\). Therefore, the closed form of the original recurrence relation is

\[\boxed{\displaystyle{a_n = \dfrac{1}{As_n} \left( A_{n = 0} s_0 a_0 + \sum_{k = 1}^n Cs_k \right)}}.\]

## Example 1: The Tower of Hanoi Problem

Find the closed form of the recurrence relation \(T_0 = 0\), \(T_n = 2T_{n-1} + 1\).

The summation factor \(s_n\) with \(A(n) = 1\) and \(B(n) = 2\) is

\[s_n = \frac{1 \times 1 \times \cdots \times 1}{2 \times 2 \times \cdots \times 2} = \frac{1}{2^{n-1}},\]

where the 1's and 2's occur \(n-1\) times each. Multiplying this to the recurrence relation gives

\[\frac{1}{2^{n-1}} T_n = \frac{1}{2^{n-2}}T_{n-1} + \frac{1}{2^{n-1}}.\]

Let \(b_n = \dfrac{1}{2^{n-1}} T_n\). Then \(b_{n - 1} = \dfrac{1}{2^{n-2}}T_{n-1}\) and \(b_0 = \dfrac{1}{2^{0-1}} T_0 = 0\). So,

\[b_n = b_{n - 1} + \frac{1}{2^{n-1}}.\]

It follows that the closed form of \(b_n\) is

\[b_n = 0 + \sum_{k = 1}^n \frac{1}{2^{k-1}} = \frac{1 \cdot \left(\frac12\right)^n - 1}{\frac12 - 1} = 2 - \frac{1}{2^{n - 1}}.\]

Note that the summation above is a finite geometric series. But since \(b_n = \dfrac{1}{2^{n-1}} T_n\), the closed form of \(T_n\) is

\[T_n = 2^{n - 1} \left( 2 - \frac{1}{2^{n - 1}} \right) = \boxed{2^n - 1}.\ _\square\]

## Example 2: The Quicksort Algorithm

Find a closed form for the recurrence relation \(C_0 = 0\), \(nC_n = (n + 1)C_{n - 1} + 2n - 2\).

Here \(A(n) = n\) and \(B(n) = n + 1\). The summation factor is thus

\[s_n = \frac{(n - 1)(n - 2)\cdots 2\cdot 1}{(n + 1)(n)\cdots 4\cdot 3} = \frac{2}{n(n+1)}.\]

Again, there are \(n - 1\) factors each in the numerator and the denominator. Multiplying \(s_n\) to the recurrence relation gives

\[\frac{2}{n+1}C_n = \frac{2}{n}C_{n - 1} + \frac{4n-4}{n(n + 1)} = \frac{2}{n}C_{n - 1} + \left( \frac{8}{n+1} - \frac{4}{n} \right)\]

by partial fraction decomposition. Now let \(b_n = \frac{2}{n+1}C_n\), so that \(b_{n-1} = \frac{2}{n}C_{n - 1}\) and \(b_0 = \frac{2}{0+1}C_0 = 0\). Hence,

\[b_n = b_{n - 1} + \left( \frac{8}{n+1} - \frac{4}{n} \right)\]

from which the closed form of \(b_n\) is given by

\[b_n = 0 + \sum_{k = 1}^n \left( \frac{8}{k+1} - \frac{4}{k} \right) = \sum_{k = 1}^n \frac{4}{k + 1} + \sum_{k = 1}^n \left( \frac{4}{k+1} - \frac{4}{k} \right).\]

Note that the second summation on the RHS telescopes as

\[\sum_{k = 1}^n \left( \frac{4}{k+1} - \frac{4}{k} \right) = \frac{4}{n + 1} - 4.\]

On the other hand, if we let \(\displaystyle{H_n = \sum_{k = 1}^n \frac{1}{k}}\) be the \(n^\text{th}\)

harmonic number(the sum of the reciprocals of the first \(n\) positive integers), we now write the first summation on the RHS as\[\sum_{k = 1}^n \frac{4}{k + 1} = \sum_{k = 2}^{n + 1} \frac{4}{k} = \sum_{k = 1}^{n + 1} \frac{4}{k} - \frac{4}{1} = 4H_{n+1} - 4.\]

Therefore,

\[b_n = (4H_{n + 1} - 4) + \left(\frac{4}{n + 1} - 4\right) = 4H_{n + 1} + \frac{4}{n + 1} - 8.\]

Since \(b_n = \frac{2}{n+1}C_n\), we now have the closed form of \(C_n\)

\[C_n = \frac{n + 1}{2}\left( 4H_{n + 1} + \frac{4}{n + 1} - 8 \right) = \boxed{2(n + 1)H_{n + 1} + 2 - 4(n + 1)}.\]

If desired, we can rewrite \(C_n\). Since \(H_{n + 1} = H_n + \frac{1}{n + 1}\), we obtain

\[C_n = 2(n + 1)\left(H_n + \dfrac{1}{n + 1} \right) + 2 - 4(n + 1) = 2(n + 1)H_n + 2 + 2 - 4n - 4 = \boxed{2(n + 1)H_n - 4n}.\ _\square\]

## Example 3

Let \(f\) be a function that satisfies the equation

\[(n + 1)^2 f(n) - n^3 f(n - 1) = 1\]

for all nonnegative integers \(n\) with \(f(0) = 3\). Find \(f(n)\).

Rewriting the equation as

\[(n+1)^2 f(n) = n^3 f(n - 1) + 1,\]

we see that \(A = (n+1)^2\) and \(B = n^3\). Thus, the summation factor \(s_n\) is

\[s_n = \frac{n^2 (n-1)^2 (n-2)^2 \cdots 2^2}{n^3 (n-1)^3 (n-2)^3 \cdots 2^3} = \frac{1}{n(n-1)(n-2)\cdots 2 \cdot (1)}=\frac{1}{n!}.\]

Multiplying \(s_n\) to the recurrence relation gives

\[\frac{(n+1)^2}{n!} f(n) = \frac{n^3}{n!} f(n-1) + \frac{1}{n!} = \frac{n^2}{(n-1)!} f(n-1) + \frac{1}{n!}.\]

Let \(b(n) = \frac{(n+1)^2}{n!} f(n)\). Then \(b(n-1) = \frac{n^2}{(n-1)!} f(n-1)\) and \(b(0) = \frac{(0+1)^2}{0!} f(0) = 3\). Thus, the new recurrence relation becomes

\[b(n) = b(n-1) + \frac{1}{n!},\]

and from this, we have the closed form of \(b(n)\) as

\[b(n) = b(0) + \sum_{k=1}^n \frac{1}{k!} = 3+\sum_{k=1}^n \frac{1}{k!}.\]

But \(b(n) = \frac{(n+1)^2}{n!} f(n)\). Therefore, the closed from of \(f(n)\) is

\[\boxed{\displaystyle{f(n) = \dfrac{n!}{(n+1)^2} \left( 3 + \sum_{k=1}^n \dfrac{1}{k!} \right)}}.\ _\square\]

## Example 4 (ongoing edit)

Let \(\{t_n\}\) be a sequence of real numbers such that \(t_0 = -1\) and

\[(n+1)t_n = t_{n-1} + (n^2 + n + 1)\]

for all integers \(n\geqslant 1\). Find the remainder when \(t_{2017}\) is divided by \(2017\).

## Problems

\[ { \begin{eqnarray} a_{n} & =& 2a_{n-1} + 3 \\ b_{n} &=& b_{n-1} + b_{n-2} \\ \end{eqnarray} } \]

For a positive integer \(n\), consider the two recurrence relations above subjected to the conditions \(a_1 = 0\) and \(b_{1} = b_{2} = 1 \).

If the value of the expression \(\big(a_{b_{2015}} + 3\big)\big(a_{b_{2016}} + 3\big)\) can be expressed as \(p^{b_{q}} \frac{r}{s}\), where \(b_{q}\) is one of the terms in the recurrence relations sequence above and \((p, r)\) and \((r, s)\) are pairwise coprime integers.

Find the value of \((p+q+r+s) \bmod {673}\).

**Cite as:**Recurrence Relations - Method of Summation Factors.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/recurrence-relations-method-of-summation-factors/