Uppgift 6
Visa med hjälp av induktion att \[
\sum_{k=1}^n k\cdot 2^{k-1} = (n-1)\cdot 2^n + 1 \tag{$\ast$}
\] gäller för alla heltal $n\geq 1$. Ange tydligt basfall samt induktionsantagande.
Diskret matematik · 2024-08-13
Uppgift 6
Visa lösningDölj lösning
Vi har basfallet $n=1$. Vänsterledet och högerledet är båda $1$ i ekvationen.
Vi antar nu att formeln ovan gäller för ett fixt värde på $n \geq 1$. Vi vill nu visa att nästföljande fall också gäller, dvs. \[ \sum_{k=1}^{n+1} k\cdot 2^{k-1} = (n)\cdot 2^{n+1} + 1. \] Vi har nu att \[ \sum_{k=1}^{n+1} k\cdot 2^{k-1} = \underbrace{\left( \sum_{k=1}^{n} k\cdot 2^{k-1} \right)}_{\text{byts ut enl. antagande}} + (n+1)\cdot 2^n = (n+1)\cdot 2^n + 1 + (n-1)\cdot 2^n. \] Högerledet kan skrivas om, \[ (n+1)\cdot 2^n + 1 + (n-1)\cdot 2^n = ((n+1)+(n-1))\cdot 2^n + 1 = 2n\cdot 2^n +1 = n\cdot 2^{n+1}+1, \] så vi har nu visat ekvationen. Basfallet samt induktionsprincipen ger nu att den slutna formeln för summan gäller för alla $n\geq 1$.
Vi antar nu att formeln ovan gäller för ett fixt värde på $n \geq 1$. Vi vill nu visa att nästföljande fall också gäller, dvs. \[ \sum_{k=1}^{n+1} k\cdot 2^{k-1} = (n)\cdot 2^{n+1} + 1. \] Vi har nu att \[ \sum_{k=1}^{n+1} k\cdot 2^{k-1} = \underbrace{\left( \sum_{k=1}^{n} k\cdot 2^{k-1} \right)}_{\text{byts ut enl. antagande}} + (n+1)\cdot 2^n = (n+1)\cdot 2^n + 1 + (n-1)\cdot 2^n. \] Högerledet kan skrivas om, \[ (n+1)\cdot 2^n + 1 + (n-1)\cdot 2^n = ((n+1)+(n-1))\cdot 2^n + 1 = 2n\cdot 2^n +1 = n\cdot 2^{n+1}+1, \] så vi har nu visat ekvationen. Basfallet samt induktionsprincipen ger nu att den slutna formeln för summan gäller för alla $n\geq 1$.