Matematisk induktion

Kurs: M0065M Förkunskaper: Logik och bevisföring

---

För att bevisa att en utsaga $P(n)$ gäller för alla heltal $n\ge n_0$:

1. Basfall: visa $P(n_0)$.
2. Induktionssteg: antag $P(k)$ och visa $P(k+1)$.

Då gäller $P(n)$ för alla $n\ge n_0$.

Summan $1+2+\cdots +n=n(n+1)/2$

Basfall ($n=1$): $1=1\cdot 2/2$. ✓ Induktionssteg: antag likheten för $n=k$. Då

$$1+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}.$$

Se även

• Talföljder och summor
• Logik och bevisföring

Resurser

• 3Blue1Brown: Induction (proof by induction)