Demostrando $\sum_{k=1}^n k k!=(n+1)!-1$

Question

Probar: $\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$ (preferiblemente combinatoria)

Es bastante fácil pensar en una historia para el RHS: organizar $n+1$ personas en una fila y quitar la opción de todo el mundo dispuestos a la altura de menor a mayor, pero no por el lado izquierdo.

Alternativamente, tratando de visualizar la LHS, me di cuenta de que es como un ángulo recto tetraedros:

1

2!+2!

3!+3!+3!

...

Pero no ayuda a ver una conexión a la RHS.

Nota: no integrales o de la función gamma, ni tampoco el uso de otras identidades, sin demostrar ni la generación de funciones.

Answer 1

$\sum_{k=1}^n{kk!}$

$=\sum_{k=1}^n{((k+1)-1)k!}$

$=\sum_{k=1}^n{(k+1)k!-k!}$

$=\sum_{k=1}^n{(k+1)!-k!}$

$=(n+1)!-1!$

$=(n+1)!-1$

Answer 2

Para una permutación $\pi = \pi_1 \ldots \pi_{n+1}$$S_{n+1}$, vamos a $m = m(\pi)$ ser el máximo índice tal que $\pi_1 = 1, \pi_2 = 2, \ldots, \pi_m = m$. El número de permutaciones tal que $m(\pi) = m$$m < n$$(n-m) (n-m)!$: aquí $n-m$ es el número de opciones para $\pi_{m+1} \neq m+1$, e $(n-m)!$ es el número de permutaciones de los restantes $n-m$ números. No permutación satisface $m(\pi) = n$, y hay una sola permutación tal que $m(\pi) = n+1$. En total, ya hay $(n+1)!$ permutaciones en $S_{n+1}$, $$ (n+1)! = \sum_{m=0}^{n-1} (n-m)(n-m)! + 1 = \sum_{k=1}^n k \cdot k! + 1. $$

Answer 3

Dada una lista ordenada de $n+1$ artículos, pick $k$$1$$n$. Centrar la atención en la primera $k$ artículos. Elija uno de estos elementos ($k$ maneras de hacer esto) para intercambiar con el elemento $k+1$. Ahora permutar esta modificación de la configuración inicial de $k$ elementos ($k!$ maneras de hacer esto), y dejar sin cambios los elementos más allá de la posición $k+1$. Cada una selección de $k$ genera una colección diferente de permutaciones. Por otra parte, como $k$ rangos de$1$$n$, vamos a generar todas las permutaciones posibles de la lista, excepto los de la lista original, ya que el algoritmo de las fuerzas de al menos un elemento para mover a una nueva posición. Conclusión: $$\sum_{k=1}^n kk! = (n+1)! - 1$$

Answer 4

Usted puede mostrar $$\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$$ by induction. It holds for $n=1.$ Assume it is satisfied for a given $n$ and show it for $n+1.$ We assume $$\displaystyle\sum_{k=1}^n k k!=(n+1)!-1$$ y tenemos que mostrar

$$\displaystyle\sum_{k=1}^{n+1} k k!=(n+2)!-1.$$ Acaba de escribir

$$\displaystyle\sum_{k=1}^{n+1} k k!=\sum_{k=1}^{n} k k!+(n+1)(n+1)!.$$ Uso hipótesis de inducción y listo.

Answer 5

Nota: me doy cuenta de que usted dijo que su solución deseada es una combinatoria de uno, pero yo pensaba que iba a proporcionar una completa inducción de la prueba en caso de que no se obtiene ningún tipo de combinatoria respuestas.

Reclamo: Para todos los $n\geq 1, \sum_{k=1}^n kk! = (n+1)!-1$.

Prueba. Deje $S(n)$ denotar la declaración de $$ S(n) : \sum_{k=1}^n kk! = (n+1)!-1. $$ Base de el paso ($n=1$): $S(1)$ es cierto porque las $1=2!-1$.

Inductivo paso: Para algunos fijos $\ell\geq 1$, asumir la hipótesis inductiva $S(\ell)$ a ser cierto $$ S(\ell) : \sum_{k=1}^\ell kk! = (\ell+1)!-1. $$ Para ser mostrado es que $S(\ell+1)$ sigue, donde $$ S(\ell+1) : \sum_{k=1}^{\ell+1} kk! = (\ell+2)!-1. $$ Comenzando con el lado izquierdo de $S(\ell+1)$, \begin{align} \sum_{k=1}^{\ell+1} kk! &= \sum_{k=1}^\ell kk! + (\ell+1)(\ell+1)!\tag{by definition of %#%#%}\\[1em] &= [(\ell+1)!-1]+(\ell+1)(\ell+1)!\tag{by %#%#%}\\[1em] &= (\ell+1)!(1+\ell+1)-1\\[1em] &= (\ell+2)\cdot(\ell+1)!-1\\[1em] &= (\ell+2)!-1, \end{align} vemos que el lado derecho de la $\Sigma$ sigue. Esto completa el paso inductivo.

Así, por inducción matemática, la declaración de $S(\ell)$ es cierto para todos $S(\ell+1)$. $S(n)$