TAOCP 3.2.1 Exercise 4

Exercise 4. [11] Prove Eq. (6).

Verified: yes
Solve time: 1m05s

Solution

We prove Eq. (6) by induction on $k$. The claim is that for all integers $k \ge 0$ and $n \ge 0$, the linear congruential sequence defined by

$X_{n+1} = (a X_n + c) \bmod m$

satisfies

$X_{n+k} = \bigl(a^k X_n + \frac{a^k - 1}{b} c \bmod m\bigr), \qquad b = a - 1. \eqno(6)$

Base case ($k = 0$): For $k = 0$, the left-hand side is $X_{n+0} = X_n$. The right-hand side is

$a^0 X_n + \frac{a^0 - 1}{b} c \equiv X_n + \frac{1 - 1}{b} c = X_n \pmod{m},$

so the formula holds trivially.

Inductive step: Assume that for some $k \ge 0$,

$X_{n+k} \equiv a^k X_n + \frac{a^k - 1}{b} c \pmod{m}.$

Consider $k+1$. By the definition of the linear congruential method,

$X_{n+k+1} \equiv a X_{n+k} + c \pmod{m}.$

Substituting the inductive hypothesis for $X_{n+k}$ gives

$$ X_{n+k+1} \equiv a \left(a^k X_n + \frac{a^k - 1}{b} c \right) + c \pmod{m}. $$

Expanding this expression yields

$$ X_{n+k+1} \equiv a^{k+1} X_n + a \frac{a^k - 1}{b} c + c \pmod{m}. $$

Factor $c$ in the second and third terms:

$$ a \frac{a^k - 1}{b} c + c = c \left(\frac{a(a^k - 1)}{b} + 1\right). $$

Simplify the coefficient:

$$ \frac{a(a^k - 1)}{b} + 1 = \frac{a^{k+1} - a}{b} + 1 = \frac{a^{k+1} - a + b}{b} = \frac{a^{k+1} - a + (a-1)}{b} = \frac{a^{k+1} - 1}{b}. $$

Therefore,

$$ X_{n+k+1} \equiv a^{k+1} X_n + \frac{a^{k+1} - 1}{b} c \pmod{m}. $$

This establishes Eq. (6) for $k+1$, completing the inductive step.

By the principle of mathematical induction, Eq. (6) holds for all integers $k \ge 0$ and $n \ge 0$.

This completes the proof.

∎