Evaluating the expression: $\sum\limits_1^n(-1)^{k-1}\frac{n \choose k}{k^2}$

Per the title, I want to evaluate the expression:

$$S = \sum\limits_{k=1}^n(-1)^{k-1}\frac{n \choose k}{k^2}$$

Looked on Approach0 but no luck.

I think it has a nice closed form:

$$S = n^2\sum\frac{1}{i^2}+\left(n\sum \frac{1}{i}\right)^2$$

My attempt:

Using the Binomial theorem:

$$\frac{1-(1-x)^n}{x} = \sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}{x^{k-1}}$$

Integrate both sides from $0$ to $x$.

$$\int\limits_0^x \frac{1-(1-x)^n}{x}dx = \sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}\frac{x^{k}}{k}$$

For the LHS, let $1-x=u$

EDIT: as pointed out by FDP, this is where the issue was. Limits of the integral need to be changed as well. See answer below for correct version.

$$\int\limits_x^0 \frac{1-(u)^n}{1-u}(-du) = \sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}\frac{x^{k}}{k}$$

$$=>\int\limits_0^x \left(\sum\limits_{k=0}^{n-1}u^{k} \right)du = \sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}\frac{x^{k}}{k}$$

$$=>\sum\limits_{k=1}^{n}\frac{x^k} {k} = \sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}\frac{x^{k}}{k}$$

$$=>\sum\limits_{k=1}^{n}\frac{x^{k-1}} {k} = \sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}\frac{x^{k-1}}{k}$$

Integrating both sides from $0$ to $1$,

$$=>\int\limits_0^1\sum\limits_{k=1}^{n}\frac{x^{k-1}} {k} = \int\limits_0^1\sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}\frac{x^{k-1}}{k}$$

$$=>\sum\limits_{k=1}^{n}\frac{1} {k^2} = \sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}\frac{1}{k^2}\tag{1}$$

Equation (1) is incorrect as evidenced by substituting $n=2$. Where did I go wrong?

Why do I care about this? It comes up in calculating the variance of the generalized coupon collector's problem. See here.

Solution 1:

The general expression given in comments can write $$S_n=\sum\limits_{k=1}^n(-1)^k\frac{n \choose k}{k^2}=\frac{\psi ^{(1)}(n+1)}{2}-\frac{\left(H_n\right){}^2}{2}-\frac{\pi ^2}{12}$$

For large enough values of $n$, you could use asymptotics and get $$S_n=\frac{1}{12} \left(6 \log ^2\left({n}\right)-12 \gamma \log \left({n}\right)-\pi ^2-6 \gamma ^2\right)-\frac{\log \left({n}\right)+\gamma -1}{2 n}+\frac{2 \log \left({n}\right)+2 \gamma -9}{24 n^2}+O\left(\frac{1}{n^3}\right)$$ which is in relative error lower than $0.1$% if $n \geq 4$ and lower than $0.01$% if $n \geq 7$ .

Solution 2:

Per comment by @FDP, I managed to correct the Math. Starting over:

Using the Binomial theorem:

$$\frac{1-(1-t)^n}{t} = \sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}{t^{k-1}}$$

Integrate both sides from $0$ to $x$.

$$\int\limits_0^x \frac{1-(1-t)^n}{t}dx = \sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}\frac{x^{k}}{k}$$

For the LHS, let $1-t=u$

$$\int\limits_1^{1-x} \frac{1-(u)^n}{1-u}(-du) = \sum\limits_{k=1}^n (-1)^{k-1}{n \choose k}\frac{x^{k}}{k}$$

$$\frac{\sum\limits_{k=1}^n\frac{1-(1-x)^k}{k}}{x} = \sum\limits_{k=1}^n (-1)^{k-1} \frac{n\choose k}{k}x^{k-1}$$

Integrate both sides from $0$ to $1$, we get:

$$\sum\limits_{k=1}^n \frac 1 k \int\limits_0^1 \frac{1-(1-x)^k}{x} dx = \sum \frac{n \choose k}{k^2} (-1)^{k-1}$$

Substituting $1-x=t$ in the integral and expanding the geometric series we get:

$$\sum\limits_{k=1}^n \frac 1 k \sum\limits_{j=1}^k \frac 1 j = \sum \frac{n \choose k}{k^2} (-1)^{k-1} = \sum\limits_{k=1}^n\sum\limits_{j=1}^k \frac {1}{jk}$$

This can very easily be extended to $k^r$ in the denominator: $$\sum_{k=1}^n(-1)^{k-1}\frac{n\choose k}{k^r}=\sum_{i_1<i_2<\dots <i_r}\frac{1}{i_1 i_2 \dots i_r}$$

and the following code verifies this upto three terms in the denominator:

def binom_trms(n,r):
    summ = 0
    for k in range(1,n+1):
        summ += (-1)**(k-1)*comb(n,k)/k**r
    return summ


def inverses_3(n):
    summ = 0
    for i in range(1,n+1):
        for j in range(1,i+1):
            for k in range(1,j+1):
                summ+=1/i/j/k
    return summ


def inverses_2(n):
    summ = 0
    for i in range(1,n+1):
        for j in range(1,i+1):
            summ+=1/i/j
    return summ