Demostrar la fórmula de desviación por inducción

Question

Encontré esto en mi libro de matemáticas. He resuelto el ejercicio a). El ejercicio b) consiste en demostrar la suma de derivación por inducción.

Un trastorno de $n$ es una permutación en la que ninguno de los elementos conserva su ubicación original. Sea $a_n$ sea el número de posibles derivaciones de n elementos.

a) Demuestre que $a_1=0$ , $a_2=1$ . Escribe todas las derivaciones de los elementos en $(A,B,C)$ y los elementos en $(A,B,C,D)$ . Demuestre que la fórmula de recursión es: $a_n = (n-1)(a_{n-1} + a_{n-2})$

Mi respuesta: Para colocar el elemento $1$ hay $(n-1)$ posibilidades. Si el campo $i$ no toma el elemento 1, hay un elemento prohibido para cada campo, y hay $a_{n-1}$ posibilidades que quedan. Si el campo $i$ toma el elemento $1$ el problema se reduce a $a_{n-2}$ . Por ello, la fórmula es $a_n = (n-1)\left(a_{n-1} + a_{n-2}\right)$ .

b) Demuestre por inducción que: $a_n=n!\left[1 - \frac{1}{1!} + \frac{1}{2!} -... + (-1)^n\frac{1}{n!}\right]$ .

Mis pensamientos: Sé cómo demostrarlo por el principio de inclusión y exclusión, pero no por inducción. Supongo que se puede utilizar la fórmula de recursión de a).

Answer 1

En realidad es sencillo. Está claro que la fórmula es válida para 1 y 2. Supongamos que la fórmula se cumple para $1 \leq k \leq n$ y demostrar que se mantiene para $n+1$ $$\begin{align} a_{n+1} &= n \cdot (a_n + a_{n-1})\\ &= n \cdot ( n! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n} \cdot \frac1{n!}] + (n-1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] )\\ &= n \cdot ( (-1)^n + (n-1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] \cdot (n+1)) \\ &= n \cdot (-1)^n + n \cdot (n+1) \cdot (n-1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] \\ &= n \cdot (-1)^n + (-1)^n - (-1)^n + (n+1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] \\ &= (-1)^n \cdot \frac{(n+1)!}{n!} - (-1)^n + (n+1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] \\ &= (-1)^n \cdot \frac{(n+1)!}{n!} + (-1)^{n+1} \cdot \frac{(n+1)!}{(n+1)!}+ (n+1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n-1} \cdot \frac1{(n-1)!}] \\ &= (n+1)! \cdot [ 1 - \frac1{1!} + \cdots + (-1)^{n+1} \cdot \frac1{(n+1)!}] \blacksquare \\ \end{align}$$