Uppgift 5
(a)
Beräkna summan $\sum_{k=1}^n k \cdot (k!)$ för $n=1,2,3,4$.
(b)
Visa med induktion att \[
\sum_{k=1}^n k \cdot (k!) = (n+1)! - 1 \text{ om $n\geq 1$}.
\] Var noga med att formulera basfall och induktionsantagande.
Diskret matematik · 2025-11-26
Uppgift 5
Visa lösningDölj lösning
- För $n=1,2,3,4$, är summan 1, 5, 23 samt 119.
- Vi ska bevisa den slutna formeln med induktion. Basfall $n=1$: $1\cdot 1!=1=2!-1$, så identiteten gäller för $n=1$.
Induktionssteg: antag att $\sum_{k=1}^n k\cdot (k!)=(n+1)!-1$ för något $n\geq 1$. Då har vi att \[ \sum_{k=1}^{n+1} k\cdot (k!) = \left( \sum_{k=1}^{n} k\cdot (k!) \right) + (n+1)(n+1)!. \] Summan i högerledet är lika med $(n+1)!-1$ enligt induktionsantagande, så högerledet blir (med algebraiska omskrivningar): \[\begin{aligned} (n+1)!-1 + (n+1)(n+1)! &= (n+1 +1)(n+1)! - 1 \\ &= (n+2)(n+1)! -1 \\ &= (n+2)! -1. \end{aligned}\] Vi har alltså visat att \[ \sum_{k=1}^{n+1} k\cdot (k!) = (n+2)! -1, \] vilket är precis påståendet för nästföljande $n$. Detta, tillsammans med basfallet och induktionsprincipen, gör att formeln gäller för alla $n\ge 1$.