Demostrando $\sum_{k=1}^{n}{(-1)^{k+1} {{n}\choose{k}}\frac{1}{k}=H_n}$

Question

He estado tratando de probar

$$\sum_{k=1}^{n}{(-1)^{k+1} {{n}\choose{k}}\frac{1}{k}=H_n}$$

He tratado de perturbación y de inversión, pero aún nada. Incluso he intentado ampliar la suma para tratar de encontrar algún patrón que podría relacionar esta a la serie armónica, pero esto sólo parece surrealista. No puedo encontrar ninguna lógica el razonamiento detrás de esta identidad. Yo no entiendo a la Wikipedia de la prueba. ¿Hay alguna prueba que no requiere de la transformación integral?

Answer 1

En el cupón de coleccionista del problema, el valor esperado del número de $N$ de los cupones necesarios para una completa colección de $m$ tipos de cupón se puede determinar de dos maneras diferentes. En el tratamiento estándar, se espera que el número de cupones para obtener cada nuevo tipo se suman, dando el resultado de $mH_m$. Pero también podemos determinar esta expectativa más en la vida cotidiana de la distribución:

\begin{align} \def\stir#1#2{\left\{{#1\atop #2}\right\}} E[N]={}&\sum_{n=0}^\infty P(N\gt n)\\ ={}&\sum_{n=0}^\infty\left(1-\frac{m!}{m^n}\stir nm\right)\\ ={}&\sum_{n=0}^\infty\left(1-\frac{m!}{m^n}\frac1{m!}\sum_{j=0}^m(-1)^{m-j}\binom mjj^n\right)\\ ={}&\sum_{n=0}^\infty\frac1{m^n}\sum_{j=0}^{m-1}(-1)^{m-j+1}\binom mjj^n\\ ={}&\sum_{j=0}^{m-1}(-1)^{m-j+1}\binom mj\sum_{n=0}^\infty\frac{j^n}{m^n}\\ ={}&\sum_{j=1}^m(-1)^{j+1}\binom mj\sum_{n=0}^\infty\frac{(m-j)^n}{m^n}\\ ={}&\sum_{j=1}^m(-1)^{j+1}\binom mj\frac mj\\ ={}&m\sum_{j=1}^m(-1)^{j+1}\binom mj\frac1j\;. \end{align}

(Aquí se $\stir nm$ es un número de Stirling del segundo tipo.) La equiparación de los dos resultados de los rendimientos de nuestra identidad.

Tal vez la derivación aparece un poco menos opaco si queremos evitar el desvío a través de los números de Stirling y aplicar directamente inclusión-exclusión. Hay $\binom mj$ formas de seleccionar $j$ tipos de cupón que no han sido recogidos todavía, y la probabilidad de que $j$ cupón particular los tipos no han sido recogidos después de $n$ sorteos se $\left(1-\frac jm\right)^n$. Así

\begin{align} E[N]={}&\sum_{n=0}^\infty P(N\gt n)\\ ={}&\sum_{n=0}^\infty\sum_{j=1}^m(-1)^{j+1}\binom mj\left(1-\frac jm\right)^n\\ ={}&\sum_{j=1}^m(-1)^{j+1}\binom mj\sum_{n=0}^\infty\left(1-\frac jm\right)^n\\ ={}&\sum_{j=1}^m(-1)^{j+1}\binom mj\frac mj\\ ={}&m\sum_{j=1}^m(-1)^{j+1}\binom mj\frac1j\;. \end{align}

Podemos generalizar esto para obtener una expresión para $H_m-H_k$. El tratamiento estándar muestra que el valor esperado del número de $N_k$ de los cupones necesarios hasta que sólo $k$ tipos de cupón faltan es $m(H_m-H_k)$. La aplicación de la inclusión-exclusión en la forma de corolario $(7)$ en esta respuesta, este valor esperado también se puede calcular como

\begin{align} E[N_k] &= \sum_{n=0}^\infty P(N_k\gt n) \\ &= \sum_{n=0}^\infty\sum_{j=1}^m(-1)^{j+k+1}\binom{j-1}{k}\binom mj\left(1-\frac jm\right)^n \\ &= \sum_{j=1}^m(-1)^{j+k+1}\binom{j-1}{k}\binom mj\sum_{n=0}^\infty\left(1-\frac jm\right)^n \\ &= \sum_{j=1}^m(-1)^{j+k+1}\binom{j-1}{k}\binom mj\frac mj \\ &= m\sum_{j=1}^m(-1)^{j+k+1}\binom{j-1}{k}\binom mj\frac1j\;, \end{align}

rendimiento

$$ H_m-H_k=\sum_{j=1}^m(-1)^{j+k+1}\binom{j-1}{k}\binom mj\frac1j\;. $$

Answer 2

Aquí es algo elemental solución:

\begin{align*} \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} \frac{1}{k} &= \sum_{k=1}^{n} \sum_{j=k}^{n} (-1)^{k-1} \binom{j-1}{k-1} \frac{1}{k} \tag{1} \\ &= \sum_{j=1}^{n} \sum_{k=1}^{j} (-1)^{k-1} \binom{j}{k} \frac{1}{j} \tag{2} \\ &= \sum_{j=1}^{n} \frac{1}{j}. \tag{3} \end{align*}

• En $\text{(1)}$, se utilizó la identidad de $ \binom{n}{k} = \sum_{j=k}^{n} \binom{j-1}{k-1} $$1 \leq k \leq n$. Esto se desprende de la costumbre 'palo de hockey argumento'.

• En $\text{(2)}$, hemos cambiado el orden de la suma y se aplica la identidad de $\binom{j-1}{k-1}\frac{1}{k} = \frac{(j-1)!}{(j-k)!k!} = \binom{j}{k}\frac{1}{j}$$1 \leq k \leq j$.

• En $\text{(3)}$, la identidad $ \sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 $ ($n \geq 1$) se utiliza para simplificar el interior de la suma. Aviso que esto es una consecuencia directa del teorema del binomio.

---

Adenda. Me di cuenta de que mi solución puede ser considerado como una versión corta de @leonbloy's inductivo prueba (aunque se me ocurrió esto de forma independiente).

Answer 3

$\newcommand{\ángulos}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\llaves}[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{\mitad}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[2]{\,\mathrm{Li}_{#1}\left(\,{#2}\,\right)} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\parcial #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\raíz}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

El Sangchul Lee comentario está relacionado con el $\ul{first\ answer}$. De hecho, he decidido añadir otro.

1. \begin{align} &\color{#f00}{\sum_{k = 1}^{n}\pars{-1}^{k + 1}{n \choose k}\,{1 \over k}} = \sum_{k = 1}^{n}\pars{-1}^{k + 1}{n \choose k}\int_{0}^{1}x^{k - 1}\,\dd x = -\int_{0}^{1}\sum_{k = 1}^{n}{n \choose k}\pars{-x}^{k}\,{\dd x \over x} \\[3mm] = &\ -\int_{0}^{1}{\pars{1 - x}^{n} - 1\over x}\,\dd x\ \stackrel{x\ \to\ 1 - x}{=}\ \int_{0}^{1}{x^{n} - 1\over x - 1}\,\dd x = \int_{0}^{1}\sum_{k = 1}^{n}x^{k - 1}\,\dd x = \sum_{k = 1}^{n}\int_{0}^{1}x^{k - 1}\,\dd x\ \\[3mm] = &\ \sum_{k = 1}^{n}{1 \over k}\ \stackrel{\mathrm{def.}}{=} \color{#f00}{H_{n}} \end{align}

   ---

2. \begin{align} &\color{#f00}{\sum_{k = 1}^{n}\pars{-1}^{k + 1}{n \choose k}\,{1 \over k}} = \sum_{k = 1}^{\infty}\pars{-1}^{k + 1}\,{1 \over k}{n \choose n - k} = \sum_{k = 1}^{\infty}\pars{-1}^{k + 1}\,{1 \over k}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{n} \over z^{n - k + 1}}\,{\dd z \over 2\pi\ic} \\[3mm] = & \oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{n} \over z^{n + 1}}\ \overbrace{% \sum_{k = 1}^{\infty}\pars{-1}^{k + 1}\,{z^{k} \over k}} ^{\ds{=\ \ln\pars{1 + z}}}\ \,{\dd z \over 2\pi\ic} = \oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{n}\ln\pars{1 + z} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} \\[3mm] = &\ \lim_{x \to 0}\partiald{}{x}\oint_{\verts{z} = 1^{-}} {\pars{1 + z}^{n + x} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} = \lim_{x \to 0}\partiald{}{x}{x + n \choose n} = {1 \over n!}\lim_{x \to 0}\partiald{}{x} \bracks{\Gamma\pars{x + n + 1} \over \Gamma\pars{x + 1}} \\[3mm] = &\ {1 \over n!} \bracks{{\Gamma\pars{n + 1}\Psi\pars{n + 1}\Gamma\pars{1} - \Gamma\pars{1}\Psi\pars{1}\Gamma\pars{n + 1} \over \Gamma^{2}\pars{1}}} = \Psi\pars{n + 1} - \Psi\pars{1} \\[3mm] = &\ n\sum_{k = 0}^{\infty}{1 \over \pars{k + n + 1}\pars{k + 1}} = \sum_{k = 1}^{\infty}\pars{{1 \over k} - {1 \over k + n}} = \sum_{k = 1}^{n}{1 \over k}\ \stackrel{\mathrm{def.}}{=}\ \color{#f00}{H_{n}} \end{align}

Answer 4

Por inducción.

Nota primero que

$$ {n+1 \choose k}={n+1 \choose k}\frac{k}{n+1} +{n \choose k}\tag{1}$$

(permite extender la validez de esta ecuación para el intervalo de $0\le k \le n+1$ suponiendo que la convención de ${n \choose n+1}=0$)

También

$$ \sum_{k=0}^{n+1} (-1)^{k+1} {n+1 \choose k} =0 \implies \sum_{k=1}^{n+1} (-1)^{k+1} {n+1 \choose k}=1 \tag{2}$$

A continuación, supongamos $\sum_{k=1}^{n}{(-1)^{k+1} {{n}\choose{k}}\frac{1}{k}=H_n}$. Por lo tanto

$$ \begin{align} \sum_{k=1}^{n+1}(-1)^{k+1} {{n+1}\choose{k}}\frac{1}{k}&= \sum_{k=1}^{n+1}(-1)^{k+1} {{n+1}\choose{k}}\frac{1}{n+1}+\sum_{k=1}^{n+1}{(-1)^{k+1} {{n}\choose{k}}\frac{1}{k}}\\ &=\frac{1}{n+1}+H_n\\ &=H_{n+1}\end{align}$$

Para completar la inducción, compruebe que $\sum_{k=1}^{1}{(-1)^{k+1} {{1}\choose{k}}\frac{1}{k}}=1=H_1$

(Inspirado por esto, de que este es esentially un caso particular)

Answer 5

Supongamos que buscamos para comprobar que

$$\sum_{k=1}^n {n\choose k} (-1)^{k+1} \frac{1}{k} = H_n.$$

Ahora observar que

$$\frac{1}{k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \log\frac{1}{1-z} \; dz$$

donde tomamos $\epsilon < 1$, de modo que el término logarítmico es analítica.

Llegamos por la suma

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \log\frac{1}{1-z} \sum_{k=1}^n {n\elegir k} (-1)^{k+1} \frac{1}{z^k} \; dz$$

El plazo para $k=0$ rendimientos

$$-\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \log\frac{1}{1-z} = 0$$

y podemos menor $k$ a cero, consiguiendo para la suma

$$-\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \log\frac{1}{1-z} \sum_{k=0}^n {n\elegir k} (-1)^{k} \frac{1}{z^k} \; dz \\ = -\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z} \left(1-\frac{1}{z}\right)^n \log\frac{1}{1-z} \; dz \\ = -\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (z-1)^n \log\frac{1}{1-z} \; dz.$$

Ahora a poner $$\frac{z}{z-1} = w \quad\text{que}\quad z = -\frac{w}{1-w} \\ \text{y}\quad dz = - \frac{1}{(1-w)^2} dw \quad\text{y}\quad \frac{1}{1-z} = 1-w.$$

para obtener

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} (z-1)^{n+1} \frac{1}{1-z} \log\frac{1}{1-z} \; dz \\ = - \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} (1-w) \log(1-w) \frac{1}{(1-w)^2} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n+1}} \frac{1}{1-w} \log\frac{1}{1-w} \; ps.$$

Este evalúa a $$H_n$$ por la inspección desde

$$\log\frac{1}{1-z} = \sum_{q\ge 1} \frac{z^q}{q}$$

como se ha visto anteriormente.