Prueba combinatoria de $\sum_{k=0}^n k \cdot k! = (n+1)! -1$

Question

¿Hay un buen combinatoria ¿prueba de la siguiente identidad? (Es decir, demostrando que ambas partes cuentan lo mismo). $$\sum_{k=0}^n k \cdot k! = (n+1)! -1 $$ Estaba buscando en Wikipedia bonitas identidades para asignar a mis alumnos para una tarea sobre pruebas combinatorias, y pensé que esta parecía bastante inocente, pero luego me di cuenta de que no podía resolverla yo mismo.

Quizás debamos tomar el conjunto de permutaciones de $n+1$ letras y dividirlo de alguna manera inteligente (tal vez el $-1$ sugiere que se deje de lado la identidad), pero no veo qué puede ser.

Por supuesto que es muy fácil de demostrar por inducción; no es eso lo que busco.

Answer 1

$k\cdot k!$ es el número de permutaciones del $(n+1)$ símbolos $0,\,1,\,\dotsc,\, n$ tal que $k$ es el mayor símbolo que no se mantiene fijo. (Símbolo $k$ se puede asignar al $k$ lugares $0,\,\dotsc,\,k-1$ El $k$ Los símbolos más pequeños pueden colocarse arbitrariamente en el $k$ dejó plazas libres). Así que

$$\sum_{k=0}^n k\cdot k!$$

es el número de permutaciones no identitarias del $(n+1)$ símbolos. Por otro lado, ese número es, por supuesto, el número total de permutaciones de $(n+1)$ símbolos menos uno.

No es la mejor prueba combinatoria de la historia, pero meh.

Answer 2

No estoy seguro de que esto constituya una "prueba combinatoria", pero ¿has probado la prueba por inducción?

Esperamos encontrar que si la afirmación es verdadera para algún n, entonces también será verdadera para n+1.

¡S[k=0 a n+1] k.k! ¡= S[k=0 a n]k.k! ¡+ (n+1)(n+1)! ¡= (n+1)! - ¡1 + (n+1)(n+1)! ¡= (n+2)! - 1

y esto es lo que se obtiene si se sustituye n por n+1 en el lado derecho de la ecuación original.

Es trivial ver que la afirmación es verdadera para n=0, por lo tanto es verdadera para todos los números naturales.

Lo anterior es sólo una prueba a grandes rasgos, pero ¿captas la idea?

p.d. ¡siento no saber hacer las ecuaciones bien!