TAOCP 1.2.11.3 Exercise 3

Exercise 3. [M20] Derive Eq. (8) from Eq. (7).

Verified: yes
Solve time: 1m10s

Solution

From Eq. (7),

$$ \gamma(a,x)=\sum_{k\ge 0}\frac{(-1)^k x^{k+a}}{k!(k+a)}. $$

Multiply both sides by $e^x=\sum_{m\ge 0} \frac{x^m}{m!}$:

$$ e^x\gamma(a,x) =\left(\sum_{m\ge 0}\frac{x^m}{m!}\right)\left(\sum_{k\ge 0}\frac{(-1)^k x^{k+a}}{k!(k+a)}\right). $$

Collect the coefficient of $x^{n+a}$ in the Cauchy product. Writing $n=m+k$,

$$ e^x\gamma(a,x) =\sum_{n\ge 0} x^{n+a}\sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!(k+a)}. $$

Define

$$ C_n=\sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!(k+a)}. $$

The coefficient in Eq. (8) equals $1/\bigl(a(a+1)\cdots(a+n)\bigr)$. Define

$$ T_n=\frac{1}{a(a+1)\cdots(a+n)}. $$

Then

$$ T_0=\frac{1}{a}. $$

For $n\ge 1$,

$$ (a+n)T_n=T_{n-1}. $$

To obtain the same recurrence for $C_n$, start from

$$ (n+a)C_n=\sum_{k=0}^n \frac{(-1)^k(n+a)}{k!(n-k)!(k+a)}. $$

Split

$$ n+a=(n-k)+(k+a), $$

$$ (n+a)C_n=\sum_{k=0}^n \frac{(-1)^k(n-k)}{k!(n-k)!(k+a)}+\sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!}. $$

For the second sum,

$$ \sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!} =\frac{1}{n!}\sum_{k=0}^n (-1)^k \binom{n}{k} =\frac{(1-1)^n}{n!}. $$

Hence the second sum equals $0$ for $n\ge 1$.

For the first sum, rewrite

$$ \frac{n-k}{(n-k)!}=\frac{1}{(n-k-1)!}, $$

and observe that the term $k=n$ vanishes since $n-k=0$. Thus

$$ \sum_{k=0}^n \frac{(-1)^k(n-k)}{k!(n-k)!(k+a)} =\sum_{k=0}^{n-1}\frac{(-1)^k}{k!(n-1-k)!(k+a)}. $$

This equals $C_{n-1}$.

Therefore, for $n\ge 1$,

$$ (n+a)C_n=C_{n-1}. $$

Both sequences satisfy the same recurrence and initial value $C_0=T_0=1/a$, hence $C_n=T_n$ for all $n\ge 0$.

Substituting back into the Cauchy product yields

$$ e^x\gamma(a,x)=\sum_{n\ge 0} x^{n+a}\frac{1}{a(a+1)\cdots(a+n)}. $$

This completes the proof. ∎