Matemātiskā indukcija
From Wikipedia, the free encyclopedia
Matemātiskā indukcija ir pierādīšanas tehnika matemātikā. To parasti izmanto, lai pierādītu, ka kāds apgalvojums vai īpašība ir spēkā visiem naturālajiem skaitļiem.
Matemātiskā indukcija izmanto šādu principu — ja mēs zinam par kādu apgalvojumu A(n), kas ir definēts visiem naturālajiem skaitļiem n, ka:
- A(1) ir patiess;
- katram naturālam skaitlim k ir spēkā tas, ka, ja A(k) ir patiess, tad arī A(k+1) ir patiess,
tad var secināt, ka apgalvojums A(n) ir patiess visiem naturālajiem skaitļiem — no 1. punkta ir redzams, ka A(1) ir patiess. No 2. punkta var secināt, ka tā kā A(1) ir patiess, tad arī A(2) ir patiess. Atkārtoti izmantojot 2. punktu, var secināt, ka tā kā A(2) ir patiess, tad arī A(3) ir patiess. Šo procesu (2. punkta izmantošanu) var turpināt bezgalīgi, tāpēc ir iespējams izdarīt secinājumu, ka apgalvojums ir spēkā visiem naturālajiem skaitļiem.
Parasti kāda apgalvojuma A(n) pierādīšanu pēc matemātiskās indukcijas principa veic pēc šāda algoritma.
- Indukcijas bāze — pamato, ka apgalvojums ir patiess pie n=1. Šajā gadījumā skaitli 1 sauc par indukcijas bāzi.
- Induktīvais pieņēmums — tiek pieņemts, ka apgalvojums ir patiess pie n=k, kur k — jebkurš naturāls skaitlis.
- Induktīvā pāreja — pamato, ka, ja ir spēkā induktīvais pieņēmums, apgalvojums ir spēkā arī pie n=k+1.
- Secinājums — pēc matemātiskās indukcijas principa var secināt, ka apgalvojums ir spēkā visiem naturālajiem skaitļiem.
Pirmās zināmās matemātiskās indukcijas pēdas ir manāmais Eiklīda pierādījumā, ka ir bezgalīgi daudz pirmskaitļu.[1] Tomēr pirmais, kas formulējis matemātiskās indukcijas principu, bija Blēzs Paskāls savā darbā Traité du triangle arithmétique.