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
\((\alpha_n)\) and \((\beta_n)\) are two sequences defined recursively as \(\alpha_n=2 \alpha_{n-1}+1\) and \(\beta_n=8 \beta_{n-1}+1\) with \(\alpha_0=\beta_0=0.\) Find the ratio
\[ \frac{\alpha_{2016}}{\beta_{672}}.\]
Let \({a_n}\) be a sequence of real numbers such that \(a_0 = 1\) and
\[\frac{a_n}{n^2 + 5n + 6} = \frac{a_{n-1}}{n^2 + 6n + 8} + \frac{n + 1}{n^2 + 7n + 12}\]
for all integers \(n \geqslant 1\). Find \(a_{40}\).
\[ \begin{cases} \begin{align}a_1&=1\\ a_{n+1}&=2a_{n}+n2^n, \quad n\ge 1 \end{align}\end{cases}\]
Let \( \left \{a_k\right \}\) be a sequence satisfying the above condition. Find the minimum \(n\) such that \(a_n > 2^{100}\).
\[ { \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}\).