¿Cómo puedo calcular $\sum\limits_{k = 1}^n \frac{1} {k + 1}\binom{n}{k} $?

Question

Esta suma es difícil. ¿Cómo puedo calcular, sin el uso de cálculo?

$$\sum_{k = 1}^n \frac1{k + 1}\binom{n}{k}$$

Si alguien puede explicar alguna técnica para hacerlo, se lo agradecería. O consejo mediante un sistema telescópico suma, yo creo que con un telescópica podía ir, pero no sé cómo montarlo.

Answer 1

\begin{align*}\sum_{k=1}^n \binom{n}{k} \frac{1}{k+1} = \frac{1}{n+1} \sum_{k=1}^n \binom{n+1}{k+1} = \frac{2^{n+1} - 1 - (n+1)}{n+1} = \frac{2^{n+1} - n-2}{n+1}. \end{align*} El primer paso de la siguiente manera a partir de la identidad $\binom{n}{k} \frac{n+1}{k+1} = \frac{n!}{k! (n-k)!} \frac{n+1}{k+1} = \frac{(n+1)!}{(k+1)! (n-k)!} = \binom{n+1}{k+1}$. El segundo paso se utiliza el hecho de que $\sum_{k=0}^{n+1} \binom{n+1}{k} = 2^{n+1}$, si bien toma nota de que el $\binom{n+1}{0}$ $\binom{n+1}{1}$ no están incluidos en la suma.

Answer 2

He aquí un enfoque probabilístico copia de mi respuesta a una pregunta duplicada. Estoy exponer aquí (marcado como CW) para el registro. Queremos mostrar que $$ \frac{1}{2^{n+1}-1} \sum_{j=0}^n \binom{n}{j} \frac{1}{j+1} = \frac{1}{n+1}. \etiqueta{$\ast$} $$

Considere un experimento en el que podemos elegir un subconjunto no vacío ("el comité") $S \subseteq \{ 0, 1, 2, \ldots, n \}$ uniformemente al azar y elegir una $x$ uniformemente al azar de $S$ (la "cabeza" de la comisión). Entonces ambos lados contar la probabilidad de que la cabeza es $0$. Por la simetría de la cabeza es un uniforme persona al azar, por lo que es $n+1$ con una probabilidad de $\frac{1}{n+1}$. Por lo tanto, sólo queda para justificar el lado izquierdo de $(\ast)$.

La probabilidad de que el evento $E_j$ que $S$ contiene $0$ y también se $j$ otras personas de $\{ 1, 2, \ldots, n\}$ es $$ \frac{1}{2^{n+1}-1} \binom{n}{j}. $$ Acondicionado en $E_j$, la probabilidad de que la cabeza es $0$ es igual a $\frac{1}{j+1}$. [Finalmente, condicionado en el caso de que $0 \notin S$, la probabilidad de que la cabeza es $0$ es cero.] Por lo tanto, por la ley de total probabilidad, $$ \begin{align*} \Pr[\text{Head is } 0] &= \sum_{j=0}^n \Pr[E_j] \cdot \Pr[\text{Head is } 0 \mid E_j] \\ &= \sum_{j=0}^n \frac{1}{2^{n+1}-1} \binom{n}{j} \cdot \frac{1}{j+1} \end{align*} $$