Teorija, formulas, atrisināts piemērs un pārbaudes jautājumi latviešu valodā. Bezmaksas CE matemātikas sagatavošanās.
Matemātiskā indukcija ir pierādīšanas metode apgalvojumiem, kas atkarīgi no naturāla skaitļa $n$ (piem., summu formulas, dalāmība).
Ideja kā "domino efekts": ja apgāžas pirmais kauliņš un katrs kauliņš apgāž nākamo, tad apgāzīsies visi.
Metode pierāda apgalvojumu $P(n)$ visiem $n$, nepārbaudot katru atsevišķi.
1. Bāze. Pārbauda, ka apgalvojums patiess sākumā, parasti $n = 1$: $P(1)$ patiess.
2. Induktīvā pāreja. Pieņem, ka $P(k)$ patiess (induktīvais pieņēmums), un pierāda, ka tad arī $P(k+1)$ patiess.
Ja abi soļi izdarīti, apgalvojums patiess visiem naturāliem $n$.
$P(1) \;\wedge\; \big(P(k) \Rightarrow P(k+1)\big) \;\Rightarrow\; P(n)\ \forall n$
Uzdevums: Pierādi, ka $1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2}$.
1. Bāze ($n=1$): kreisā puse $= 1$; labā $= \frac{1 \cdot 2}{2} = 1$ ✓
2. Pieņēmums: pieņemam, ka $1 + \ldots + k = \frac{k(k+1)}{2}$.
3. Pāreja ($k \to k+1$): jāpierāda summa līdz $k+1$:
$$\underbrace{1 + \ldots + k}_{\frac{k(k+1)}{2}} + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$$
Tas ir tieši formula pie $n = k+1$ ✓ — pierādīts.
"Domino princips": bāze apgāž pirmo kauliņu, pāreja garantē, ka katrs apgāž nākamo → krīt visi.
Pārejā vienmēr lieto induktīvo pieņēmumu — tas ir visas metodes kodols. Atrodi summu/izteiksmi pie $k$ un "uzbūvē" $k+1$ gadījumu uz tās.
Tipisks paņēmiens: pie $k+1$ izsvītro daļu, kas pēc pieņēmuma jau zināma, un atliek pierādīt tikai pievienoto locekli.
⚠️ Bez bāzes pierādījums nav pilnīgs. Pāreja viena pati negarantē neko — vajag "pirmo kauliņu".
⚠️ Induktīvajā pārejā jāizmanto pieņēmums $P(k)$. Ja to nelieto, tas nav indukcijas pierādījums.
⚠️ Pārbaude vairākiem $n$ (piem., $n=1,2,3$) NAV pierādījums — tas tikai parāda, ka formula varētu būt patiesa. Pierāda tikai vispārīgā pāreja.