Skip to main content
edited body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

One can also use the binomial transform.

(If $A(z)=\sum_{i\geq 0} a_i z^i$ is a (formal) power series, the (formal) power series $B(z):=\frac{1}{1-z} A(\frac{z}{1-z})$ has coefficients $[z^n] B(z)=\sum_{j=0}^n {n \choose j} a_j$).

We have $\log(\frac{1}{1-z})=\sum_{k\geq 1} \frac{z^k}{k}$.

Thus \begin{align*} \sum_{k=1}^n {n \choose k}\frac{1}{k}&=[z^n] \frac{1}{1-z}\,\log\big(\frac{1}{1-\frac{1}{1-z}}\big)\\ &=[z^n] \frac{1}{1-z}\,\log\big(\frac{1-2z}{1-z}\big)\\ &=[z^n] \frac{1}{1-z}\,\Big(\log\big(\frac{1}{1-2z}\big)-\log\big(\frac{1}{1-z}\big)\Big)\\ &=\sum_{k=1}^n\frac{2^k}{k} -\sum_{k=1}^n \frac{1}{k}\end{align*}\begin{align*} \sum_{k=1}^n {n \choose k}\frac{1}{k}&=[z^n] \frac{1}{1-z}\,\log\big(\frac{1}{1-\frac{z}{1-z}}\big)\\ &=[z^n] \frac{1}{1-z}\,\log\big(\frac{1-z}{1-2z}\big)\\ &=[z^n] \frac{1}{1-z}\,\Big(\log\big(\frac{1}{1-2z}\big)-\log\big(\frac{1}{1-z}\big)\Big)\\ &=\sum_{k=1}^n\frac{2^k}{k} -\sum_{k=1}^n \frac{1}{k}\end{align*}

One can also use the binomial transform.

(If $A(z)=\sum_{i\geq 0} a_i z^i$ is a (formal) power series, the (formal) power series $B(z):=\frac{1}{1-z} A(\frac{z}{1-z})$ has coefficients $[z^n] B(z)=\sum_{j=0}^n {n \choose j} a_j$).

We have $\log(\frac{1}{1-z})=\sum_{k\geq 1} \frac{z^k}{k}$.

Thus \begin{align*} \sum_{k=1}^n {n \choose k}\frac{1}{k}&=[z^n] \frac{1}{1-z}\,\log\big(\frac{1}{1-\frac{1}{1-z}}\big)\\ &=[z^n] \frac{1}{1-z}\,\log\big(\frac{1-2z}{1-z}\big)\\ &=[z^n] \frac{1}{1-z}\,\Big(\log\big(\frac{1}{1-2z}\big)-\log\big(\frac{1}{1-z}\big)\Big)\\ &=\sum_{k=1}^n\frac{2^k}{k} -\sum_{k=1}^n \frac{1}{k}\end{align*}

One can also use the binomial transform.

(If $A(z)=\sum_{i\geq 0} a_i z^i$ is a (formal) power series, the (formal) power series $B(z):=\frac{1}{1-z} A(\frac{z}{1-z})$ has coefficients $[z^n] B(z)=\sum_{j=0}^n {n \choose j} a_j$).

We have $\log(\frac{1}{1-z})=\sum_{k\geq 1} \frac{z^k}{k}$.

Thus \begin{align*} \sum_{k=1}^n {n \choose k}\frac{1}{k}&=[z^n] \frac{1}{1-z}\,\log\big(\frac{1}{1-\frac{z}{1-z}}\big)\\ &=[z^n] \frac{1}{1-z}\,\log\big(\frac{1-z}{1-2z}\big)\\ &=[z^n] \frac{1}{1-z}\,\Big(\log\big(\frac{1}{1-2z}\big)-\log\big(\frac{1}{1-z}\big)\Big)\\ &=\sum_{k=1}^n\frac{2^k}{k} -\sum_{k=1}^n \frac{1}{k}\end{align*}

Source Link
esg
  • 3.3k
  • 11
  • 15

One can also use the binomial transform.

(If $A(z)=\sum_{i\geq 0} a_i z^i$ is a (formal) power series, the (formal) power series $B(z):=\frac{1}{1-z} A(\frac{z}{1-z})$ has coefficients $[z^n] B(z)=\sum_{j=0}^n {n \choose j} a_j$).

We have $\log(\frac{1}{1-z})=\sum_{k\geq 1} \frac{z^k}{k}$.

Thus \begin{align*} \sum_{k=1}^n {n \choose k}\frac{1}{k}&=[z^n] \frac{1}{1-z}\,\log\big(\frac{1}{1-\frac{1}{1-z}}\big)\\ &=[z^n] \frac{1}{1-z}\,\log\big(\frac{1-2z}{1-z}\big)\\ &=[z^n] \frac{1}{1-z}\,\Big(\log\big(\frac{1}{1-2z}\big)-\log\big(\frac{1}{1-z}\big)\Big)\\ &=\sum_{k=1}^n\frac{2^k}{k} -\sum_{k=1}^n \frac{1}{k}\end{align*}