Coefficient extraction

I want to show: \begin{equation*} [z^n]\frac{1}{(1-z)^{\alpha + 1}} \log \frac{1}{1-z} = \binom{n + \alpha }{n} (H_{n+\alpha} - H_{\alpha}). \end{equation*} where $[z^n]$ means the $n$-th coefficient of the power series and \begin{equation} H_{n+\alpha} - H_{\alpha} = \sum^{n}_{k=1}{\frac{1}{\alpha + k}} \end{equation} So far I got \begin{equation*} \frac{1}{(1 - z)^{\alpha + 1}} = (1-z)^{-(\alpha + 1)} = \sum_{n \geq 0}{\binom{-\alpha - 1}{k}(-1)^k z^k} = \sum_{n \geq 0}{\binom{\alpha + n }{n} z^n} \end{equation*} where I used $\binom{-\alpha}{k} = (-1)^k \binom{\alpha + k - 1}{k}$and \begin{equation*} \log \frac{1}{1 - z} = - \log 1- z = \sum_{n \geq 1}\frac{z^n}{n} = z\sum_{n \geq 0}\frac{z^{n}}{n+1} \end{equation*} therefore \begin{align*} \frac{1}{(1-z)^{\alpha + 1}} \log \frac{1}{1-z} &= z\left( \sum_{n \geq 0}{\binom{\alpha + n }{n} z^n} \right) \left( \sum_{n \geq 0}\frac{z^{n}}{n+1} \right) \\ &= z \sum_{n \geq 0}\sum^{n}_{k=0}\binom{\alpha + k}{k} \frac{1}{n - k + 1} z^{n} \\ &= \sum_{n \geq 0}\sum^{n}_{k=0}\binom{\alpha + k}{k} \frac{1}{n - k + 1} z^{n + 1}. \end{align*} Now the $n$-th coefficient is \begin{align*} \sum^{n}_{k=0}\binom{\alpha + k}{k} \frac{1}{n - k + 1} &= \binom{\alpha + n}{n} \sum^n_{k = 1}{\frac{n!}{(n-k)! k!} \frac{1}{\binom{\alpha + n}{n - k}} \frac{1}{n - k + 1}} + \frac{1}{n+1}\\ &= \binom{\alpha + n}{n} \sum^n_{k = 1}{\binom{n}{k} \frac{1}{\binom{\alpha + n}{n - k}} \frac{1}{n - k + 1}} + \frac{1}{n+1}\\ &= \binom{\alpha + n}{n} \sum^n_{k = 1}{\binom{n}{k - 1} \frac{1}{\binom{\alpha + n}{n - k - 1}} \frac{k-1}{n - k -1} \frac{1}{\alpha + k + 1} } + \frac{1}{n+1}\\ &= \binom{\alpha + n}{n} \sum^{n+1}_{k = 2}{\binom{n}{k - 2} \frac{1}{\binom{\alpha + n}{n - k}} \frac{k- 2 }{n - k} \frac{1}{\alpha + k} } + \frac{1}{n+1} \end{align*} but from now on I can't see how to proceed. I also know that \begin{equation} [z^n] \frac{1}{1-z} \log \frac{1}{1-z} = H_n \end{equation} somehow I also tried to use some sort of transformation law for coefficient extraction, but I am not aware of any kind of transformation law for coefficient extraction. Using $1-u = (1-z)^{\alpha + 1}$ or $z = 1 - (1-u)^{1/(\alpha + 1)}$gives \begin{equation} \frac{1}{\alpha + 1}\frac{1}{1-u} \log \frac{1}{1 - u} \end{equation} and for this I get the coefficient $\frac{1}{\alpha + 1} H_n$.

Another approach I did was the following:
Since \begin{equation*} (1-z)^{-m} = \exp(-m \ln(1-z)) \end{equation*} I get \begin{equation*} \frac{\partial }{\partial m} \exp(-m \ln(1-z)) = -\ln(1-z) \exp(- m \ln(1-z)) = - \ln(1-z) \frac{1}{(1-z)^m} = \frac{1}{(1-z)^m} \ln \frac{1}{1-z} \end{equation*} therefore \begin{align*} \frac{\partial }{\partial m} (1-z)^{-m} &= \sum_{n \geq 0}{\frac{\partial }{\partial m} \binom{m + n - 1}{n} z^n} \\ &= \sum_{n \geq 0}{\frac{\partial }{\partial m} \frac{\Gamma(m + n)}{n!\Gamma(m)} z^n} \end{align*} But I don't know any identities for the derivative of the gamma function.

Solution 1:

We will need an auxiliary identity before we can move on to the subject by OP, which is

$$[z^n] \frac{1}{(1-z)^{\alpha+1}} \log\frac{1}{1-z} = {n+\alpha\choose n} (H_{n+\alpha} - H_\alpha).$$

with $\alpha$ a non-negative integer.

A binomial identity

Introduce with $q\ge 1$

$$f(z) = n! (-1)^n \frac{1}{z+q} \prod_{p=0}^n \frac{1}{z-p}.$$

This has the property that for $0\le r\le n$

$$\mathrm{Res}_{z=r} f(z) = n! (-1)^n \frac{1}{r+q} \prod_{p=0}^{r-1} \frac{1}{r-p} \prod_{p=r+1}^n \frac{1}{r-p} \\ = n! (-1)^n \frac{1}{r+q} \frac{1}{r!} \frac{(-1)^{n-r}}{(n-r)!} = {n\choose r} \frac{(-1)^r}{r+q}.$$

With the residue at infinity being zero by inspection we obtain

$$\sum_{r=0}^n {n\choose r} \frac{(-1)^r}{r+q} = - \mathrm{Res}_{z=-q} f(z) \\ = - n! (-1)^n \prod_{p=0}^n \frac{1}{-q-p} = n! \prod_{p=0}^n \frac{1}{q+p} = n! \frac{(q-1)!}{(q+n)!} = \frac{1}{q} {n+q\choose q}^{-1}.$$

Therefore with $1\le k\le n$

$$\frac{1}{k} {n\choose k}^{-1} = \sum_{r=0}^{n-k} {n-k\choose r} \frac{(-1)^r}{r+k} = (-1)^{n-k} \sum_{r=0}^{n-k} {n-k\choose r} \frac{(-1)^r}{n-r} \\ = [z^n] \log\frac{1}{1-z} (-1)^{n-k} \sum_{r=0}^{n-k} {n-k\choose r} (-1)^r z^r \\ = [z^n] \log\frac{1}{1-z} (-1)^{n-k} (1-z)^{n-k}.$$

Main identity

We get for the LHS from first principles that it is (apply identity setting $n$ to $n+\alpha$ and $k$ to $q$)

$$\sum_{q=1}^n {n-q+\alpha\choose n-q} \frac{1}{q} \\ = [z^{n+\alpha}] \log\frac{1}{1-z} \sum_{q=1}^n {n+\alpha\choose q} {n-q+\alpha\choose \alpha} (-1)^{n+\alpha-q} (1-z)^{n+\alpha-q}.$$

Note that for $q=0$ we get

$${n+\alpha\choose \alpha} [z^{n+\alpha}] \log\frac{1}{1-z} (-1)^{n+\alpha} (1-z)^{n+\alpha}.$$

This will be our first piece. We include it in our sum at this time. Next observe that

$${n+\alpha\choose q} {n-q+\alpha\choose \alpha} = \frac{(n+\alpha)!}{q! \times \alpha! \times (n-q)!} = {n+\alpha\choose \alpha} {n\choose q}.$$

We have for the augmented sum without the binomial scalar in front

$$[z^{n+\alpha}] \log\frac{1}{1-z} \sum_{q=0}^n {n\choose q} (z-1)^{n+\alpha-q} \\ = [z^{n+\alpha}] \log\frac{1}{1-z} (z-1)^{n+\alpha} \left[1+\frac{1}{z-1}\right]^n \\ = [z^{n+\alpha}] \log\frac{1}{1-z} (z-1)^\alpha z^n = [z^\alpha] \log\frac{1}{1-z} (z-1)^\alpha.$$

This is the second piece. Now to evaluate these two pieces we evidently require

$$\;\underset{z}{\mathrm{res}}\; \frac{1}{z^{m+1}} \log\frac{1}{1-z} (-1)^m (1-z)^m.$$

We put $z/(1-z) = w$ so that $z=w/(1+w)$ and $dz = 1/(1+w)^2 \; dw$ to obtain

$$\;\underset{w}{\mathrm{res}}\; \frac{1}{w^{m+1}} (1+w) \log\frac{1}{1-w/(1+w)} (-1)^m \frac{1}{(1+w)^2} \\ = (-1)^m \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{m+1}} \frac{1}{1+w} \log(1+w) = (-1)^m [w^m] \frac{1}{1+w} \log(1+w) \\ = [w^m] \frac{1}{1-w} \log(1-w) = - [w^m] \frac{1}{1-w} \log\frac{1}{1-w} = - H_m.$$

Hence our first piece is $- {n+\alpha\choose\alpha} H_{n+\alpha}$ while the second is $- {n+\alpha\choose\alpha} H_{\alpha}$. Subtract the first from the second to obtain our claim,

$${n+\alpha\choose n} (H_{n+\alpha} - H_\alpha).$$

Solution 2:

Here are two different proofs of the relation

$$\begin{align}\sum _{n=0}^{\infty } z^n\binom{n+\alpha }{n}(H_{n+\alpha} -H_{\alpha})\\ =(1-z)^{-\alpha -1}\log(\frac{1}{1-z})\end{align}\tag{*} $$

which is equivalent to the claim of the OP.

1. Proof by derivate

We start from the basic binomial relation

$$\sum _{n=0}^{\infty } z^n \binom{n+\alpha }{n} = (1-z)^{-\alpha -1}\tag{1.1}$$

Differentiating $(1.1)$ with respect to $\alpha$ gives

$$\sum _{n=0}^{\infty } z^n \frac{\partial }{\partial \alpha }\binom{\alpha +n}{n} \\ =\frac{\partial (1-z)^{-\alpha -1}}{\partial \alpha }=(1-z)^{-\alpha -1}(-\log(1-z))\tag{1.2}$$

Now

$$\frac{\partial }{\partial \alpha }\binom{\alpha +n}{n}= \frac{\partial }{\partial \alpha }\frac{\Gamma(n+1+\alpha)}{\Gamma(n+1) \Gamma(\alpha+1)}\tag{1.3}$$

where $\Gamma(x+1) = (x)!$ is the gamma function.

Using

$$\frac{\partial \Gamma (y+1)}{\partial y}\\ =\Gamma (y+1) \psi ^{(0)}(y+1)=\Gamma (y+1)(H_y - \gamma)\tag{1.4}$$

where $\psi ^{(0)}$ is the polygamma function, $\gamma$ is Euler's gamma and $H_y$ is the harmonic number with argument $y$ we find

$$\frac{\partial }{\partial \alpha }\binom{\alpha +n}{n}= \binom{\alpha +n}{n}(H_{n+\alpha} -H_{\alpha}) \tag{1.5}$$

Inserting this into $(1.2)$ gives $(*)$. Q.E.D.

2. Proof by integral

Here is my originally first solution showing that the claim of the OP holds good for complex values of $\alpha$ with $\Re(\alpha) \gt -1$ rather than being restricted to non-negative integers values.

We start with the observation that the claim of the OP can be stated in the form

$$\begin{align} g(z):=\sum_{n=0}^{\infty}z^n \binom{n+\alpha}{n} (H_{n+\alpha}-H_\alpha)\\ = i(z):=\int_{0}^{1} f(x,z) \; dx \\ =r(z):=-(1-z)^{-\alpha -1} \log (1-z)\end{align}\tag{2.1}$$

where

$$f(x,z)=\frac{x^{\alpha } \left((1-z)^{-\alpha -1}-(1-x z)^{-\alpha -1}\right)}{1-x}\tag{2.2}$$

Here and in what follows the parameters are assumed to be restricted to $0 \lt z \lt 1$ and $\Re(\alpha) \gt -1$. Note that $\alpha$ need not be integer.

$g(z)$ is the generating function, $i(z)$ its integral representation, and $r(z)$ the function to which the g.f. should reduce according to the claim of the OP.

Now inserting Euler's representation of the harmonic number, $H_n = \int_{0}^{1} \frac{1-x^n}{1-x}\;dx$ into $g(z)$ and using the basic binomial identity

$$\sum _{n=0}^{\infty } z^n \binom{n+\alpha }{n}=(1-z)^{-(\alpha +1)}\tag{2.3}$$

we can easily confirm that $g(z) = i(z)$, with the integrand $f(x,z)$ given by $(2.2)$.

The tough part for me at first was to show that $i(z)=r(z)$. Mathematica showed that the equality is correct, but how to prove it?

Here's one possibility: first we write the integral as

$$(1-z)^{-\alpha -1} \int_0^1 \frac{x^{\alpha } \left(1-\left(\frac{1-x z}{1-z}\right)^{-\alpha -1}\right)}{1-x} \, dx\tag{2.4}$$

Comparison with $r(z)$ shows that is remains to prove that

$$ i_1(z)=\int_0^1 \frac{x^{\alpha } \left(1-\left(\frac{1-x z}{1-z}\right)^{-\alpha -1}\right)}{1-x} \, dx=-\log(1-z)\tag{2.5}$$

Surprisingly the integral $i_1$ must not depend on $\alpha$.

The trick is now to look at the derivative of $i_1(z)$ with respect to $z$. Taking the derivative under the integral we find the elementary integral

$$\begin{align} i_1'(z) = (\alpha +1) (1-z)^{\alpha } \int_0^1 \frac{x^{\alpha }}{(1-x z)^{\alpha +2}} \, dx\\ = (\alpha +1) (1-z)^{\alpha }\left(\frac{x^{\alpha +1} (1-x z)^{-\alpha -1}}{\alpha +1}\right)\vert _{x=0}^{x=1}=\frac{1}{1-z} \end{align}\tag{2.6}$$

Integrating and observing that $i_1(z=0)=0$ we find $i_1=-\log(1-z)$ and we obtain $i(z) = r(z)$ which completes the solution.

3. Discussion

Generalized relations for generating functions can be easily derived following the lines of proof 1 by going to higher derivatives with respect to $\alpha$.

Skipping the details we have from the second derivative:

$$\begin{align}\sum _{n=0}^{\infty } z^n \binom{n+\alpha }{n} \left(\left(H_{n+\alpha }-H_{\alpha }\right){}^2+\left(H_{\alpha }^{(2)}-H_{n+\alpha }^{(2)}\right)\right)\\ =(1-z)^{-\alpha -1} \log ^2(1-z)\end{align}\tag{3.1}$$

Here we have used this replacement of the polygamma function by the (generalized) harmonic number $\psi ^{(1)}(1+t)=-(H_t^{(2)} - \zeta(2))\tag{3.2}$

Generally for $m \ge 1$ we have this replacement

$$\psi ^{(m)}(t+1)\to (-1)^m m! \left(H_t^{(m+1)}-\zeta (m+1)\right)\tag{3.3}$$

An so forth. Each derivative generates a new power of $-\log(1-z)$ and a combination of products of generalized harmonic numbers. The $\zeta$-functions from the replacements $(3.3)$ drop out.

The reader is invited to find the general expression for the $k$-th derivative. Here are the first steps towands this goal.

We need the higher drivatives of the polygamma function $\psi(\alpha)^{(k)}$ which we abbreviate as $\psi_k$ and of the gamma function $\Gamma$. The first part is easy. By definition we have

$$\frac{\partial }{\partial \alpha }\psi_k=\psi_{k+1}\tag {3.4}$$

The difficult part is

$$\frac{\partial^k }{\partial \alpha ^k}\Gamma=?$$

The first few derivatives are

$$\frac{\partial}{\partial \alpha }\Gamma=\Gamma \psi_0$$ $$\frac{\partial^2 }{\partial \alpha ^2}\Gamma=\psi_0\Gamma' +\Gamma \psi_1=\psi_0^2 \Gamma +\Gamma \psi_1= \Gamma (\psi_0^2+\psi_1)$$ $$\frac{\partial^3 }{\partial \alpha ^3}\Gamma=\frac{\partial }{\partial \alpha}\Gamma (\psi_0^2+\psi_1)=\Gamma \psi_0(\psi_0^2+\psi_1) +\Gamma (2\psi_0 \psi_1+\psi_2)=\Gamma\left(\psi_0^3 + 3\psi_0\psi_1+\psi_2\right)$$

We can derive a recursion relation for the m-th derivative $\Gamma ^{(m)}$ of $\Gamma=\Gamma ^{(0)}$ as follows: from $\frac{\partial}{\partial \alpha }\Gamma=\Gamma \psi_0$ we have $\frac{\partial^{k+1}}{\partial \alpha ^{k+1}}\Gamma=\frac{\partial^{k}}{\partial \alpha ^{k}}\Gamma\psi_0$

which, by expanding the derivative of the product binomically, leads to the recursion relation

$$\frac{\partial^{k+1}}{\partial \alpha ^{k+1}}\Gamma = \sum_{m=0}^{k} \binom{k}{m}\Gamma^{(m)}\psi_{k-m}\tag{3.5}$$

Notice that the sequence of coefficients $1; 1,1; 1,3,1; 1,6,4,3,1; ...$ of the aggregates in $\psi$ appear in OEIS http://oeis.org/A178867 with the description "Irregular triangle read by rows: multinomial coefficients, version 3; alternatively, row n gives coefficients of the n-th complete exponential Bell polynomial B_n(x_1, x_2, ...) with monomials sorted into some unknown order."

The interested researcher can can discover several things to add to that entry, e.g. the formula in Mathematica, and comment on the order topic.

Solution 3:

Here is another variation. We show the identity \begin{align*} \color{blue}{[z^n]\frac{1}{(1-z)^{\alpha+1}}\log\frac{1}{1-z}=\binom{n+\alpha}{n}\sum_{k=1}^n\frac{1}{\alpha+k}}\tag{1} \end{align*} is valid for integral $n>0$ and $\alpha \in\mathbb{C}\setminus\{-1,\ldots,-n\}$.

We start with the LHS of (1) and obtain \begin{align*} \color{blue}{[z^n]}\color{blue}{\frac{1}{(1-z)^{\alpha+1}}\log\frac{1}{1-z}} &=[z^n]\frac{1}{(1-z)^{\alpha+1}}\sum_{k=1}^\infty\frac{z^k}{k}\tag{2.1}\\ &=\sum_{k=1}^n\frac{1}{k}[z^{n-k}]\frac{1}{(1-z)^{\alpha+1}}\tag{2.2}\\ &=\sum_{k=1}^n\frac{1}{k}\binom{-\alpha-1}{n-k}(-1)^{n-k}\tag{2.3}\\ &\,\,\color{blue}{=\sum_{k=1}^n\frac{1}{k}\binom{n+\alpha-k}{n-k}}\tag{2.4} \end{align*}

Comment:

• In (2.1) we use the logarithmic series expansion.

• In (2.2) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$ and restrict the upper limit of the sum to $n$, since other terms do not contribute.

• In (2.3) we select the coefficient of $[z^{n-k}]$ of the binomial series expansion.

• In (2.4) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

It remains to show the binomial identity \begin{align*} \color{blue}{\sum_{k=1}^n\frac{1}{k}\binom{n+\alpha-k}{n-k}=\binom{n+\alpha}{n}\sum_{k=1}^n\frac{1}{\alpha+k}}\tag{3} \end{align*}

A nice aspect is, that when considering the expressions in (3) as polynomial in $\alpha$ we can show, that they both are the derivative $\frac{\partial}{\partial\alpha}\binom{n+\alpha}{n}$.

We start with the RHS of (3) which is the easy part. We obtain \begin{align*} \color{blue}{\frac{\partial}{\partial \alpha}}\color{blue}{\binom{n+\alpha}{n}} &=\frac{1}{n!}\frac{\partial}{\partial \alpha}\prod_{j=0}^{n-1}(n+\alpha-j)\tag{4.1}\\ &=\frac{1}{n!}\frac{\partial}{\partial \alpha}\prod_{j=0}^{n-1}(\alpha+j+1)\tag{4.2}\\ &=\frac{1}{n!}\frac{\partial}{\partial \alpha}\prod_{j=1}^{n}(\alpha+j)\tag{4.3}\\ &=\frac{1}{n!}\sum_{k=1}^n\left(\frac{\partial}{\partial \alpha}(\alpha+k)\right)\prod_{{j=1}\atop {j\ne k}}^n(\alpha+j)\tag{4.4}\\ &=\frac{1}{n!}\sum_{k=1}^n\frac{1}{\alpha+k}\prod_{j=1}^n(\alpha+j)\tag{4.5}\\ &\,\,\color{blue}{=\binom{n+\alpha}{n}\sum_{k=1}^n\frac{1}{\alpha+k}} \end{align*} and we get the RHS of (3).

Comment:

• In (4.1) we use the definition of binomial coefficients in the form $\binom{p}{q}=\frac{1}{q!}\prod_{j=0}^{q-1}(p-j)$.

• In (4.2) we change the order of multiplication $j\to n-1-j$.

• In (4.3) we shift the index and start with $j=1$.

• In (4.4) we use the product rule for derivation of products with $n$ terms.

• In (4.5) we do the derivation and expand numerator and denominator with $\alpha+k$.

Now the somewhat more challenging part. We do the derivation by using first principles. We obtain \begin{align*} \color{blue}{\frac{\partial}{\partial \alpha}}&\color{blue}{\binom{n+\alpha}{n}} =(-1)^n\frac{\partial}{\partial \alpha}\binom{-\alpha-1}{n}\tag{5.1}\\ &=(-1)^n\lim_{q\to 0}\frac{1}{q}\left(\binom{-\alpha-1-q}{n}-\binom{-\alpha-1}{n}\right)\tag{5.2}\\ &=(-1)^n\lim_{q\to 0}\frac{1}{q}\left(\sum_{k=0}^n\binom{-q}{k}\binom{-\alpha-1}{n-k}-\binom{-\alpha-1}{n}\right)\tag{5.3}\\ &=(-1)^n\lim_{q\to 0}\frac{1}{q}\sum_{k=1}^n\binom{-q}{k}\binom{-\alpha-1}{n-k}\\ &=(-1)^n\lim_{q\to 0}\frac{1}{q}\sum_{k=1}^n\frac{-q}{k}\binom{-q-1}{k-1}\binom{-\alpha-1}{n-k}\tag{5.4}\\ &=(-1)^{n+1}\sum_{k=1}^n\frac{1}{k}\binom{-1}{k-1}\binom{-\alpha-1}{n-k}\\ &=\sum_{k=1}^n\frac{(-1)^{n-k}}{k}\binom{-\alpha-1}{n-k}\tag{5.5}\\ &\,\,\color{blue}{=\sum_{k=1}^n\frac{1}{k}\binom{n+\alpha-k}{n-k}}\tag{5.6} \end{align*} which is the LHS of (3) and the claim (3) follows.

Comment:

• In (5.1) we use again the binomial identity as in (2.4).

• In (5.2) we do the derivation according to first principles.

• In (5.3) we apply the Chu-Vandermonde identity.

• In (5.4) we use the binomial identity $\binom{p}{q}=\frac{p}{q}\binom{p-1}{q-1}$.

• In (5.5) we use the binomial identity $\binom{-1}{q}=\frac{1}{q!}(-1)(-2)\cdots(-q)=(-1)^q$.

• In (5.6) we use again the binomial identity as in (2.4).

Solution 4:

Perhaps similar to epi163sqrt's answer in that this uses Vandermonde's Identity. However, this avoids the use of a derivative.

Using the power series $$ \log\left(\frac1{1-z}\right)=\sum_{k=1}^\infty\frac{z^k}{k}\tag1 $$ and the Generalized Binomial Theorem with negative binomial coefficents $$ \begin{align} (1-z)^{-\alpha-1} &=\sum_{k=0}^\infty\binom{-\alpha-1}{k}(-1)^kz^k\tag{2a}\\ &=\sum_{k=0}^\infty\binom{k+\alpha}{k}z^k\tag{2b} \end{align} $$ we get $$ \begin{align} &\left[z^n\right] (1-z)^{-\alpha-1}\log\left(\frac1{1-z}\right)\tag{3a}\\ &=\sum_{k=0}^{n-1}\frac1{n-k}\binom{k+\alpha}{k}\tag{3b}\\ &=\binom{n+\alpha}{n}\sum_{k=0}^{n-1}\frac1{n-k}\frac{\binom{k+\alpha}{k}}{\binom{n+\alpha}{n}}\tag{3c}\\ %&=\binom{n+\alpha}{n}\sum_{k=0}^{n-1}\frac1{n-k}\frac{\frac{(k+\alpha)\dots(1+\alpha)}{k!}}{\frac{(n+\alpha)\dots(1+\alpha)}{n!}}\tag{3d}\\ &=\binom{n+\alpha}{n}\sum_{k=0}^{n-1}\frac1{n-k}\frac{n\dots(k+1)}{(n+\alpha)\dots(k+1+\alpha)}\tag{3d}\\ &=\binom{n+\alpha}{n}\sum_{k=0}^{n-1}\frac1{n-k}\frac{\binom{n}{n-k}(n-k)!}{(n+\alpha)\dots(k+1+\alpha)}\tag{3e}\\ &=\binom{n+\alpha}{n}\sum_{k=0}^{n-1}\frac{\binom{n}{n-k}(n-k-1)!}{(n+\alpha)\dots(k+1+\alpha)}\tag{3f}\\ &=\binom{n+\alpha}{n}\sum_{k=0}^{n-1}\sum_{j=k+1}^n\frac1{j+\alpha}\frac{\binom{n}{n-k}(n-k-1)!}{(n-j)\dots1(-1)(k+1-j)}\tag{3g}\\ &=\binom{n+\alpha}{n}\sum_{j=1}^n\sum_{k=0}^{j-1}\frac1{j+\alpha}(-1)^{j-k-1}\binom{n}{n-k}\binom{n-k-1}{j-k-1}\tag{3h}\\ &=\binom{n+\alpha}{n}\sum_{j=1}^n\sum_{k=0}^{j-1}\frac1{j+\alpha}\binom{n}{k}\binom{j-n-1}{j-k-1}\tag{3i}\\ &=\binom{n+\alpha}{n}\sum_{j=1}^n\frac1{j+\alpha}\tag{3j}\\ &=\binom{n+\alpha}{n}\left(H_{n+\alpha}-H_\alpha\right)\tag{3k} \end{align} $$ Explanation:
$\text{(3b)}$: $(1)$, $(2)$, and the Cauchy Product Formula
$\text{(3c)}$: factor $\binom{n+\alpha}{n}$ out front
$\text{(3d)}$: expand and cancel the binomial coefficients
$\text{(3e)}$: rewrite the product in the numerator
$\text{(3f)}$: cancel the $n-k$ in the numerator and denominator
$\text{(3g)}$: apply partial fractions
$\text{(3h)}$: collect the factors into $(-1)^{j-k-1}\binom{n-k-1}{j-k-1}$
$\text{(3i)}$: apply negative binomial coefficients
$\text{(3j)}$: apply Vandermonde's Identity
$\text{(3k)}$: rewrite the sum as a difference of Extended Harmonic Numbers