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$.

---