Prueba combinatoria $\sum_{i=1}^n i/(i + 1)! = 1 - 1/(n+1)!\quad\forall n\in\mathbb N$

Question

Estoy tratando de encontrar una prueba combinatoria (o al menos parcialmente combinatoria) de la ecuación $$\sum_{i=1}^n \frac i{(i + 1)!} = 1 - \frac 1{(n+1)!}\quad\forall n\in\mathbb N$$

Estoy pensando que el lado derecho se puede transformar en $\frac {(n + 1)! - 1} {(n + 1)!}$ donde el numerador representa el número de permutaciones de (n + 1) objetos menos una permutación particular. El lado izquierdo puede transformarse entonces en $\frac {n + \sum_{i=1}^{n-1} i(i + 2)(i + 3)...(n + 1)}{(n + 1)!}$ donde aparentemente el numerador también debería ser igual a ese número. No puedo entender por qué.

Answer 1

Para cualquier permutación $\sigma$ de $m$ elementos, considerados como una longitud $m$ secuencia de enteros entre $1$ y $n+1$ , dejemos que $I(\sigma)$ es igual al mayor número entero $I$ tal que $1,2,\dots,I$ aparecen en orden en la secuencia (ignorando los elementos intermedios). Por ejemplo, $I(5,4,3,2,1)=1$ , $I(5,1,4,3,2) = 2$ , $I(1,4,2,5,3)=3$ , $I(5,1,2,3,4)=4$ y $I(1,2,3,4,5)=5$ . En general $I(\sigma)$ es un número entero entre $1$ y $m$ , inclusive.

La probabilidad de que $I(\sigma) \ge i$ es exactamente $\frac1{i!}$ (suponiendo que la longitud de la permutación en cuestión sea al menos $i$ ), ya que el grupo simétrico en $i$ actúa sobre las permutaciones permutando donde $1,\dots,i$ son y dejar el resto en paz. Por lo tanto, la probabilidad de que $I(\sigma) = i$ es exactamente $\frac1{i!} - \frac1{(i+1)!} = \frac i{(i+1)!}$ .

Ahora vemos que la identidad $$ \sum_{i=1}^n \frac i{(i+1)!} + \frac1{(n+1)!} = 1 $$ es expresar las probabilidades de que una permutación $\sigma$ en $n+1$ elementos tiene $I(\sigma)=i$ $(i=1,\dots,n)$ o $I(\sigma)=n+1$ .

Answer 2

Note : En caso de que alguien decida votar negativamente esta respuesta, por favor deje un comentario explicando lo que podría haber hecho mejor (eso asegurará que mi próxima respuesta evite los mismos escollos que ésta)

Respuesta :

Si multiplicamos el lado izquierdo (LHS) por $(n+1)!$ obtenemos una suma de una serie de términos cuyo término i's es-

$$ T(i)= i*\frac{(n+1)!}{(i+1)!} = i*P(n+1,(n+1)-(i+1)) $$ y $$ LHS * (n+1)! = \sum_{i=1}^n T(i) $$

où $P(j,k)$ representa el número de permutaciones de $j$ objetos distintos tomados $k$ a la vez.

Poniendo $x=n+1$ , escribiendo $i$ en el multiplicador como $(i+1-1)$ y simplificando -

$$T(i)= ((i+1)-1) * P(x,x-(i+1))$$

$$T(i)= (i+1) * P(x,x-(i+1)) - P(x,x-(i+1))$$

El primer término de la ecuación anterior puede simplificarse utilizando la notación factorial, lo que simplifica aún más -

$$T(i)= P(x,x-i) - P(x,x-(i+1)) $$

Observe cómo $T(i)$ representa la diferencia entre el número de permutaciones de $x$ objetos tomados $(x-i)$ objetos a la vez y tomados $(x-i-1)$ objetos a otro. ( Tenga en cuenta también que $x-i$ y $x-i-1$ representan números enteros consecutivos que varían en la serie de $T(i)$ términos de $n$ a $1$ como $i$ varía de $1$ a $n$ )

Por lo tanto, la suma acumulada de todas estas diferencias daría la diferencia entre el mayor y el menor número de permutaciones de $(n+1)$ que aparecen como primer y último término, respectivamente, en el $T(i)$ serie como $i$ va de $1$ a $n$ .

$$LHS*(n+1)! = \sum_{i=1}^n T(i) = P(n+1,n)-P(n+1,1) = (n+1)!-1$$

Dividiendo ambos lados por $(n+1)!$ ,

$$LHS = 1-\frac{1}{(n+1)!} = RHS$$ que es el resultado deseado.

Espero que esto ayude.

Answer 3

Sugerencia

$f(r)=\frac{1}{r!}$ y $f(r+1)=\frac{1}{r+1!}$

$f(r)-f(r+1)=\frac{r}{r+1!}$

Answer 4

Considere la $(n+1)!$ permutaciones $\sigma$ de $\{1,2,\dots,n+1\}$ .

Cuente el número de $\sigma$ tal que $\sigma(1)<\sigma(2)<\dots<\sigma(i)$ pero $\sigma(i)>\sigma(i+1)$ : hay $\frac{(n+1)!}{(i+1)!}$ opciones de $\sigma(i+2),\dots,\sigma(n+1)$ y para cada una de esas elecciones, $\sigma(i+1)$ puede ser cualquiera de los restantes $i+1$ números excepto el más grande, y luego $\sigma(1),\dots,\sigma(i)$ se determinan. Así que hay $\frac{(n+1)!i}{(i+1)!}$ posibilidades.

Pero hay una $\sigma$ ( $\sigma(i)=i$ para todos $i$ ) que no se cuenta cuando sumamos sobre $i$ , por lo que la suma es $(n+1)!-1$ .