Matemātiskā indukcija ir īpašs veids, kā pierādīt matemātisku patiesību. To var izmantot, lai pierādītu, ka kaut kas ir patiess visiem naturālajiem skaitļiem (visiem veseliem pozitīvajiem skaitļiem). Ideja ir tāda, ka

  • Kaut kas attiecas uz pirmo gadījumu
  • Tas pats vienmēr attiecas arī uz nākamo gadījumu.

tad

  • Tas pats attiecas uz visiem gadījumiem.

Rūpīgā matemātikas valodā:

  • Norādiet, ka pierādījums tiks veikts ar indukciju pār n {\displaystyle n}n . ( n {\displaystyle n}n ir indukcijas mainīgais.)
  • Pierādiet, ka apgalvojums ir patiess, ja n {\displaystyle n}n ir 1.
  • Pieņemsim, ka apgalvojums ir patiess jebkuram dabiskajam skaitlim n {\displaystyle n}n . (To sauc par indukcijas soli.)
    • Tad parādiet, ka šis apgalvojums ir patiess arī nākamajam n + 1 skaitlim {\displaystyle n+1}{\displaystyle n+1} .

Tā kā tas ir taisnība attiecībā uz 1, tad tas ir taisnība attiecībā uz 1+1 (=2, pēc indukcijas soļa), tad tas ir taisnība attiecībā uz 2+1 (=3), tad tas ir taisnība attiecībā uz 3+1 (=4) un tā tālāk.

Indukcijas pierādījuma piemērs:

Pierādiet, ka visiem dabiskajiem skaitļiem n:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)} {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)}

Pierādījums:

Pirmkārt, apgalvojumu var rakstīt šādi: visiem dabiskajiem skaitļiem n

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)} {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)}

Pēc indukcijas uz n,

Pirmkārt, n=1:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)},

tāpēc tas ir taisnība.

Tālāk pieņemsim, ka kādam n=n0 apgalvojums ir patiess. Tas ir,:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)}

Tad, ja n=n0+1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{{n_{0}}}+1}k}} {\displaystyle 2\sum _{k=1}^{{n_{0}}+1}k}

var pārrakstīt

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)} {\displaystyle 2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)}

Tā kā 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),} {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),}

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)}

Tādējādi pierādījums ir pareizs.

Kas īsti notiek — vienkāršā skaidrojuma kopsavilkums

  • Bāzes gadījums (base case): parādām, ka apgalvojums ir patiess kādam sākuma naturālam skaitlim (parasti n = 1, bet var būt arī cita vērtība).
  • Indukcijas solis (inductive step): pieņemam, ka apgalvojums ir patiess kādam n = n0 (indukcijas pieņēmums) un pierādām, ka tad tas ir patiess arī n = n0 + 1. Tas parāda, ka patiesība „pāriet” no vienas vērtības uz nākamo.
  • Secinājums: ja bāzes gadījums ir patiess un apgalvojums pāriet no n uz n+1, tad tas ir patiess visiem turpmākajiem naturālajiem skaitļiem.

Papildu piemērs — pirmo n nepāra skaitļu summa

Pierādīsim, ka pirmo n nepāra skaitļu summa ir n^2, t.i.,

1 + 3 + 5 + ... + (2n−1) = n^2

Pierādījums:

  • Bāzes gadījums: n = 1 => 1 = 1^2 — taisnība.
  • Indukcijas solis: pieņemam, ka 1 + 3 + ... + (2n0−1) = n0^2. Tad pievienojot nākamo nepāra skaitli 2(n0+1)−1 = 2n0+1, iegūstam:

    1 + 3 + ... + (2n0−1) + (2n0+1) = n0^2 + (2n0+1) = (n0+1)^2.

    Tas parāda, ka ja apgalvojums ir patiess n0, tad tas ir patiess arī n0+1.

Tāpēc pēc matemātiskās indukcijas apgalvojums ir patiess visiem naturālajiem n.

Stiprā indukcija un citas variācijas

  • Stiprā indukcija: šeit inducēšanas solī drīkst pieņemt, ka apgalvojums ir patiess visiem k ≤ n0, nevis tikai k = n0. To lieto, ja nepieciešams izmantot vairākus iepriekšējos gadījumus, ne tikai tieši iepriekšējo.
  • Sākuma indeksa izvēle: bāzes gadījums var sākties nevis ar 1, bet ar jebkuru naturālu skaitli m; tad pierādījums pierāda apgalvojumu visiem n ≥ m.
  • Indukcija uz citām struktūrām: indukcijas ideja vispārināma: grafiem, vektoru garumiem, reizinājumiem u.c. (piem., strukturālā indukcija datorzinātnē).

Padomi un biežākās kļūdas

  • Skatieties uzmanīgi bāzes gadījumu — ja tas nav pareizi izvēlēts vai pierādīts, indukcija neveic savu darbu.
  • Indukcijas solī vajag skaidri izmantot indukcijas pieņēmumu un pareizi izrēķināt izteiksmes, lai pārliecinātos, ka tiešām iegūst apgalvojumu priekš n+1.
  • Nepierādiet n+1 ar apgalvojumu „tas ir acīmredzami” — parādiet skaitliskās vai algebriskās pārejas soļus.
  • Ja izmantojat stipro indukciju, paskaidrojiet, kāpēc ir nepieciešams pieņēmums par visiem iepriekšējiem gadījumiem.

Kad izvēlēties indukciju

Indukcija ir noderīga, ja apgalvojums ir skaidri definēts rekursīvi vai ja, lai pierādītu nākamo gadījumu, nepieciešama informācija par iepriekšējo gadījumu(-iem). Tipiski piemēri: summas formulas, reizinājumu identitātes, dalāmības apgalvojumi, skaitliskās rindas un daži kombinatorikas apgalvojumi.

Kopsavilkums

Matemātiskā indukcija ir spēcīgs un vienkāršs instruments, kas ļauj pierādīt apgalvojumu par visiem naturālajiem skaitļiem, ja var parādīt bāzes gadījumu un to, ka patiesība pāriet no n uz n+1. Izmantojiet skaidru struktūru: bāzes gadījums → indukcijas pieņēmums → indukcijas solis, un pārliecinieties, ka visi soļi ir izskaidroti un pareizi izrēķināti.