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.

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)}}.\]

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\]

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\]

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\]

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\).

---