3
$\begingroup$

I came across the following problem, let $N![z^N]A(z)$ denote the coefficient of an exponential generating function (EGF) $A(z)$. The EGF is similar to an ordinary generating function (OGF) $A'(z)$ except that instead of the series $A'(z)=\sum_0^Na_Nz^N$ for an OGF, we have $A(z)=a_Nz^N/N!$ for an EGF $A(z)$.

For instance, for EGF $A(z)=e^z$, we have $N![z^N]A(z)=N![z^N]e^z=1$, i.e. the EGF coefficients of $e^z$ are $1$ for all $N \in \mathbb{N}$, i.e. the coefficients of the set $ \{z^0/0!,z^1/1!,z^2/2!,...,z^N/N! \}$ are all $1$ for any $N$ given $e^z$. Similarly, for EGF $A(z)=1/(1-z)$, we have $N!z[^N](1/(1-z))=N!$.

Now, given the following EGF $A(z)$:

$$ A(z)=e^z\int^z_0\frac{1-e^{-t}}{t}dt $$

We are supposed to get $N![z^N]A(z)=H_N$, where $H_N$ is the $N$th harmonic number, i.e.

$$ N![z^N]e^z\int^z_0\frac{1-e^{-t}}{t}dt = H_N $$

I could not think of a way to prove the above statement. The problem gave a hint that proving this statement involves forming a differential equation for the EGF $H(z)=\sum_{N \geq 0}H_Nz^N/N!$...

Any help?

$\endgroup$
1
  • 1
    $\begingroup$ Your expression for the EGF of the harmonic number can be written in terms of standard functions as $A(z) = e^z (\gamma+\Gamma(0,z)+\log(z))$, where $\gamma$ is Euler's gamma and $\Gamma(0,z)$ is the imcomplete gamma function. $\endgroup$ Jun 1, 2020 at 19:49

2 Answers 2

3
$\begingroup$

I think "forming a differential equation" is an overkill. We can simply do $$A(z)=\int_0^z\frac{e^z-e^{z-t}}{t}\,dt\underset{t=z(1-x)}{\phantom{\big[}=\phantom{\big]}}\int_0^1\frac{e^z-e^{zx}}{1-x}\,dx=\sum_{n=1}^{\infty}\frac{z^n}{n!}\int_0^1\frac{1-x^n}{1-x}\,dx=\sum_{n=1}^{\infty}H_n\frac{z^n}{n!}$$ (the last equality, if unknown to you, follows from $(1-x^n)/(1-x)=1+\ldots+x^{n-1}$).

A side note: if we directly multiply the series for $e^z$ and the integral, we get $$A(z)=\left(\sum_{n=0}^{\infty}\frac{z^n}{n!}\right)\left(\sum_{n=1}^{\infty}\frac{(-1)^{n-1}z^n}{n\cdot n!}\right)=\sum_{n=1}^{\infty}\frac{z^n}{n!}\sum_{k=1}^{n}\binom{n}{k}\frac{(-1)^{k-1}}{k},$$ i.e. another proof of the "frequent" $G_1=H_1$ case of this question of mine.

$\endgroup$
2
  • $\begingroup$ thanks, just to ask, could you explain how the third equality happened ? $\endgroup$
    – Link L
    Jun 1, 2020 at 3:50
  • 1
    $\begingroup$ @LinkL: we substitute $e^z=\sum\limits_{n=0}^{\infty}\frac{z^n}{n!}$ and $e^{zx}$ similarly; the terms with $n=0$ cancel. $\endgroup$
    – metamorphy
    Jun 1, 2020 at 3:51
1
$\begingroup$

Here is a proof involving forming a differential equation.


Let $H_n$ be the $n^\text{th}$ harmonic number. In particular, $H_0=0$ and $H_n=\frac1n+H_{n-1}$ for $n\geq 1$.

Define the series $B(t)=\sum_{n\geq 0} H_{n+1}\frac{t^n}{n!}$. Let $A(z) = \int_0^z B(t)dt$. One observation is that: $$A(t)=\sum_{n\geq 0} H_n\frac{t^n}{n!}\label{1} \tag{1}.$$

With that in mind: \begin{align*} B(t) &= \sum_{n\geq 0} H_{n+1}\frac{t^n}{n!} \\ &= \sum_{n\geq 0}\left(\frac1{n+1} + H_n\right)\frac{t^n}{n!} \\ &= t^{-1}\sum_{n\geq 1}\frac{t^n}{n!} + \sum_{n\geq 0}H_n\frac{t^n}{n!} \\ &= t^{-1}(e^t-1) + \int_0^t B(s)ds. \\ \end{align*}

In other words, $A'(t)-A(t) = t^{-1}(e^t-1)$. This is a $1^\text{st}$ order linear ODE.

By multiplying both sides by the integrating factor $e^{-t}$, we get: \begin{align*} [e^{-t}A(t)]' = t^{-1}(1-e^{-t}). \end{align*} Integrate both sides from $t=0$ to $t=z$ and rearrange to find: $$A(z)=e^z\int_0^z \frac{1-e^{-t}}{t}dt.$$

Using (\ref{1}), we can see that $n![z^n]A(z)=H_n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.