# 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.

• It is $$\frac{1}{12} \left(-6 \psi ^{(0)}(n+1)^2-12 \gamma \psi ^{(0)}(n+1)+6 \psi ^{(1)}(n+1)-\pi ^2-6 \gamma ^2\right)$$ Commented Nov 14, 2019 at 19:09
• Hmm, so no nice expression. What's wrong with my approach? Commented Nov 14, 2019 at 19:14
• When you perform the change of variable $u=1-t$, $\displaystyle \int_0^x\dfrac{1-(1-t)^n}{t}\,dt$ the result is $\displaystyle \int_{1-x}^1\dfrac{1-u^n}{1-u}\,du$
– FDP
Commented Nov 14, 2019 at 20:53
• A special case of this question of mine. Commented Nov 14, 2019 at 21:05
• @FDP Good catch. Commented Nov 14, 2019 at 21:37

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$$ .

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

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

• I suppose that you need to multiply the last term by $-1$. Commented Nov 15, 2019 at 6:50
• Right, fixed. Thanks! Commented Nov 15, 2019 at 6:53
• @user90369 - thanks, fixed all the things you pointed out. Commented Nov 15, 2019 at 8:57

$$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$$ \begin{align} &\bbox[10px,#ffd]{\sum_{k = 1}^{n}\pars{-1}^{k - 1}{{n \choose k} \over k^{2}}} = \sum_{k = 1}^{n}\pars{-1}^{k - 1}{n \choose k} \bracks{-\int_{0}^{1}\ln\pars{x}x^{k - 1}\,\dd x} \\[5mm] = &\ \int_{0}^{1}\ln\pars{x}\sum_{k = 1}^{n}{n \choose k}\pars{-x}^{k} \,{\dd x \over x} = \int_{0}^{1}{\ln\pars{x}\bracks{\pars{1 - x}^{n} - 1} \over x}\,\dd x \\[5mm] & = \left.\partiald{}{\mu}\int_{0}^{1}\bracks{x^{\mu - 1}\pars{1 - x}^{n} - x^{\mu - 1}} \,\dd x\,\right\vert_{\ \mu\ =\ 0^{\large +}} \\[5mm] = &\ \partiald{}{\mu}\bracks{{\Gamma\pars{\mu}\Gamma\pars{n + 1} \over \Gamma\pars{\mu + n + 1}} - {1 \over \mu}}_{\ \mu\ =\ 0^{\large +}} \\[5mm] = &\ \partiald{}{\mu}\braces{{1 \over \mu}\bracks{{\Gamma\pars{\mu + 1} \Gamma\pars{n + 1} \over \Gamma\pars{\mu + n + 1}} - 1}} _{\ \mu\ =\ 0^{\large +}} \\[5mm] = &\ {1 \over 2}\,\partiald[2]{}{\mu}\bracks{{\Gamma\pars{\mu + 1} \Gamma\pars{n + 1} \over \Gamma\pars{\mu + n + 1}} - 1} _{\ \mu\ =\ 0^{\large +}} \\[5mm] = &\ \left.{1 \over 2}\,\Gamma\pars{n + 1}\,\partiald[2]{}{\mu} {\Gamma\pars{\mu + 1} \over \Gamma\pars{\mu + n + 1}}\right\vert_{\ \mu\ =\ 0^{\large +}} \\[5mm] = &\ \bbx{\large {\pi^{2} \over 12} + {1 \over 2}\,H_{n}^{2} - {1 \over 2}\,\Psi\, '\pars{n + 1}} \\[5mm] &\ \end{align}