---
kurs:
  - M0065M
tags:
  - matematik
  - logik
  - bevis
förkunskaper:
  - "[[Logik och bevisföring]]"
status: true
aliases:
  - Induktion
  - Induktionsbevis
---
> **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$.

> [!example]- 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)](https://youtu.be/CMWFmjlB8v0)