9. NODAĻA

PAREIZU APGALVOJUMU KĻŪDAINI PIERĀDĪJUMI UN OTRĀDI

UZMANĪBU- SLIDENS !

Iepriekšējās nodaļās mēs aplūkojām dažādas indukcijas shēmas. Tās pilnībā apgūstot, iespējams risināt ļoti daudzus sarežģītus uzdevumus ievērojami vienkāršāk nekā ar citām metodēm. Tomēr tieši šī vienkāršība bieži vien rada kļūdas, kuru galvenais cēlonis ir formāla indukcijas shēmu pielietošana.

Šajā paragrāfā apkopoti kļūdaini "pierādījumi", kas izpildīti ar matemātisko indukciju. Katrs piemērs ilustrē kādu tipisku, bieži sastopamu kļūdu. Parādīti gan pareizu apgalvojumu nepareizi "pierādījumi", gan arī nepareizu apgalvojumu "pierādījumi".

Vispirms aplūkosim nepareizi izdarītu induktīvo pāreju.

72. piemērs. Pierādīt: katram naturālam n un jebkuriem pozitīviem skaitļiem a₁, a₂, …, a_n, kuru reizinājums ir 1, ir pareiza nevienādība

(1+a₁)(1+a₂) …(1+a_n).=2ⁿ.

Šis apgalvojums ir patiess, bet "pierādījums", kuru aplūkosim,- kļūdains.

Bāze. Ja n=1, iegūstam atsevišķu apgalvojumu "ja a₁=1, tad 1+a₁₂¹". Protams, tas ir patiess.

Pāreja. kk+1. Pieņemsim, ka apgalvojums ir patiess, ja n=k, t.i., pieņemsim, ka

Aplūkosim tādus k+1 skaitļus a₁,a₂…, a_k,a_k+1, kuriem a₁a₂…, a_ka_k+1=1, un pierādīsim, ka (1+a₁)(1+a₂)…(1+a_k)(1+a_k+1)2^k+1. Tiešām, izmantojot induktīvo pieņēmumu, ja a₁,a₂,…, a_k=1, tad arī un 1+a_k+1=2, tā kā (1+a₁)…(1+a_k)2^k.pēc induktīvā pieņēmuma, tad

Šajā "risinājumā" nepareizi tiek izmantots induktīvais pieņēmums. Pierādot, ka apgalvojums patiess, ja n=k+1, drīkst izmantot

1. noteikumu par dotajiem k+1 skaitļiem, t.i., vienādību a₁,a₂,…, a_k, a_k+1=1;
2. induktīvo hipotēzi "a₁,a₂,…, a_k=1, ja a₁,a₂,…, a_k=1, tad (1+a₁)…(1+a_k)2^k".

Diemžēl no tā, ka a₁, a₂,…, a_k+1=1, nevar secināt, ka arī a₁, a₂,…, a_k=1, tātad nav arī zināms, vai (1+a₁)(1+a₂)…(1+a_k)2^k. Šo nevienādību drīkstēsim izmantot tikai tad, ja būs zināms, ka a₁, a₂,…, a_k=1.

Induktīvā hipotēze ir nosacīts apgalvojums "ja …, tad…", no tā, ka šāds nosacīts apgalvojums ir patiess (ko mēs pierādījumā ar indukciju pieņemam), neseko ka " ja …" tiešām izpildās. Piemēram, no tā, ka ir patiess apgalvojums "ja es spētu aizlēkt tālumā 10 metrus, es būtu pasaules rekordists", nevar izdarīt secinājumu "es spēju aizlēkt tālumā 10 metrus" un uz šī secinājuma balstīt tālākos spriedumus par savu nākotni sportā.

Aplūkotajā piemērā kļūda radās no nepareizas "apiešanās" ar induktīvo hipotēzi: mēs centāmies no tās iegūt vairāk, nekā iespējams.

Nākošajā piemērā kļūdas cēlonis būs induktīvās hipotēzes nelikumīga pielietošana ārpus pieļaujamām robežām.

75. piemērs. "Pierādīsim", ka visi naturālie skaitļi ir vienādi.

Ar max(x; y) apzīmēsim lielāko no skaitļiem x un y. Piemēram, max(2; 3)=3 max(4; 2)=4, max(4; 4)=4.

Acīmredzot apgalvojums būs pierādīts, ja būs pierādīta lemma: jebkuriem naturāliem skaitļiem x, y un n no vienādības max(x; y)=n izriet vienādība x=y.

Tiešām, pieņemsim, ka šī lemma pierādīta. Aplūkosim kaut kādus naturālus skaitļus a un b. Ja ab, izraudzīsimies x=a, y=b, n=a; tad pēc lemmas a=b. Ja a<b, izraudzīsimies x=a, y=b, n=b; tad pēc lemmas a=b.

Atliek pierādīt lemmu.

Bāze. Ja n=1, iegūstam apgalvojumu "max(x; y)=1, tad x=y".

Šis apgalvojums ir patiess, jo naturālo skaitļu kopā neviens elements nav mazāks kā 1. Tāpēc, ja max(x; y)=1, tad x=1 un y=1, tātad x=y.

Pāreja kk+1. Pieņemsim, ka lemma pareiza, ja n=k, t.i., pieņemsim, ka patiess apgalvojums "ja un y- naturāli skaitļi un max(x; y)=k, tad x=y".

Pierādīsim lemmu, ja n=k+1, t.i., pierādīsim apgalvojumu "ja x un y naturāli skaitļi un max(x; y)=k+1, tad x=y".

Izraudzīsimies kaut kādus naturālus skaitļus x un y, kuriem ir pareiza vienādība

No šīs vienādības izriet, ka

bet tad pēc induktīvās hipotēzes x-1=y-1 un tātad x=y, ko arī vajadzēja pierādīt. Tā kā x un y- brīvi izraudzīti naturālie skaitļi, kuriem max(x; y)=k+1, tad induktīvā pāreja pierādīta un līdz ar to pierādīta arī lemma.

Šoreiz kļūda radusies tādēļ, ka nav ievēroti visi induktīvās hipotēzes noteikumi: x-1 un y-1 jābūt naturāliem skaitļiem, bet, ja, piemēram, x=1 vai y=1, tad x-1 (vai y-1) nav narurāls skaitlis.

Abi nākošie piemēri ilustrēs kļūdas, kas saistītas ar nepietiekami plašas indukcijas Bāzes pierādīšanu.

76. piemērs. "Pierādīsim" vēlreiz, ka visi naturālie skaitļi ir vienādi.

Acīmredzot apgalvojums būs pierādīts, ja būsim pierādījuši šādu lemmu:

ja uz katras no n kartiņām uzrakstīts kāds naturāls skaitlis, tad uz visām kartiņām uzrakstītie skaitļi ir vienādi (n- jebkurš naturāls skaitlis).

Pierādīsim šo lemmu ar indukciju pēc n.

Bāze. Ja n=1, lemma acīmredzot pareiza.

Pāreja kk+1. Pieņemsim, ka lemma pierādīta, ja n=k. Aplūkosim uz k+1 kartiņām uzrakstītus skaitļus a₁,a₂, …, a_k, a_k+1. Izņemsim no komplekta kartiņu, uz kuras uzrakstīts skaitlis a_k+1. Uz atlikušajām k kartiņām uzrakstīties skaitļi vienādi pēc induktīvās hipotēzes, tātad

a1=a2= …=ak

(1)

Atliksim atpakaļ komplektā kartiņu ar skaitli a_k+1 un izņemsim no tā kartiņu ar skaitli a₁. Uz atlikušajām k kartiņām uzrakstītie skaitļi arī savā starpā ir vienādi pēc induktīvās hipotēzes, tātad

a2=a3= …=ak=ak+1

(2)

No nevienādībām (1) un (2) izriet, ka

a1=a2= …=ak=ak+1,

(3)

t.i., apgalvojums ir patiess, ja n=k+1. Indukīvā pāreja izdarīta, un tātad lemma pierādīta.

Lemmas pierādījums ir kļūdains, jo indukcijas bāze nav pietiekama. Aplūkoto induktīvo pāreju var izdarīt tikai tad, ja k2.

Tiešām, šādai induktīvajai pārejai nepieciešami vismaz trīs skaitļi- divi skaitļi, ko katru citā reizē atliek malā no komplekta, un trešais skaitlis, kas abas reizes paliek komplektā un tātad ir vienāds ar katru no atliekamajiem skaitļiem. Ja šāda trešā skaitļa- "vienojoša posma"starp abiem malā atliktajiem skaitļiem- nav, prasīto vienādību pierādīt nevar. Tātad k+13, k2. Līdz ar to indukcijas bāze šādā spriedumā jāpierāda arī, ja n=2 (ne tikai ar n=1). Skaidrs, ka to izdarīt nevar.

77. piemērs. "Pierādīsim", ka a^n-1=1 katram pozitīvam a un jebkuram naturālam n.

Bāze. Ja n=1, jāpierāda vienādība a⁰=1. Tātad ir pareiza.

Pāreja. "<kk". Pieņemsim, ka apgalvojums ir pareizs, ja n=1, 2, …, k-2, k-1, t.i., ka vienādības a^1-1=1, a^2-1=1, …, a^(k-2)-1=1, a^(k-1)-1=1 ir pareizas katram pozitīvam skaitlim a.

Pierādīsim, ka apgalvojums ir patiess arī tad, ja n=k, t.i., ka

Tiešām, pēc induktīvās hipotēzes

.

Izmantojot 3. teorēmu, secinām, ka apgalvojums ir patiess.

Kļūda radusies tāpēc, ka formāli pielietota 3. teorēma (ja A(1) ir patiess un no tā, ka A(n) patiess visiem n<k, izriet A(k) patiesums, tad A(n) patiess visiem naturāliem n). Induktīvā pāreja būtu pierādīta skaitļiem k>2(k-2N tikai tad, ja k>2!), ja būtu pietiekama indukcijas bāze: lai aplūkoto induktīvo pāreju iegūtu vienādību a^3-1=1, jāizmanto vienādības a^2-1=1 un a^1-1=1, bet pierādīta ir tikai pēdējā vienādība.

Uzdevumi paškontrolei IX

Atrast kļūdas 156. un 157. uzdevuma "pierādījumos".

156. Ja, x₁+x₂+ …+x_n=0, tad (1+x₁)(1+x₂) …(1+x_n)1. (Šis apgalvojums ir patiess.)

Bāze. Ja n=1, tad x₁=0, tāpēc 1+x₁=11.

Pāreja. kk+1. Pieņemsim, ka apgalvojums ir patiess, ja n=k, t.i., jax_11,…x_{n1 un} x₁+x₂+ …+x_k=0, tad (1+x₁)(1+x₂) …(1+x_k)1. Pierādīsim, ka tas patiess arī tad, ja n=k+1. Tiešām, aplūkosim k+1 skaitļus x_1, x₂,…,x_k, x_k+1, kas apmierina sakarības x_11,x_21,…,x_k1, x_k+11, x₁+…+x_k+x_k+1=0. No nosacījumiem x₁+x₂+…+x_k+x_k+1=0 un x₁+x₂+…+x_k=0 iegūstam x_k+1=0, tāpēc

pēc induktīvās hipotēzes. Pāreja pierādīta.

157. Jebkuri n punkti atrodas uz vienas taisnes.

Bāze. Ja n=1 (un arī, ja n=2), apgalvojums patiess.

Pāreja kk+1. Pieņemsim, ka apgalvojums patiess, ja n=k.

Aplūkosim k+1 punktus A₁, A₂, …, A_k, A_k+1. Punkti A₁, A₂, …, A_k atrodas uz vienas taisnes pēc induktīvā pieņēmuma; apzīmēsim šo taisni ar l₁. Punkti A₂, …, A_k, A_k+1 (skaitā k) atrodas uz vienas taisnes pēc induktīvā pieņēmuma; apzīmēsim šo taisni ar l₂. Tā kā gan l₁, gan l₂ iet caur punktiem A₂ un A_k, bet caur diviem punktiem var novilkt tikai vienu taisni, tad l₁ un l₂ sakrīt. Līdz ar to induktīvā pāreja pierādīta.

158. Izskaidrojiet šādu paradoksu.

Sestdien, lasot pēdējo lekciju, pasniedzējs teica studentiem: "Nākošajā nedēļā kādu dienu pulksten 13.00, trešās lekcijas laikā, uzdošu jums kontroldarbu. Pirms tam jūs neviens nezināsiet, kurā dienā kontroldarbs tiks uzdots. Turklāt kontroldarbu uzdošu tikai vienreiz."

Studenti ar matemātikas indukcijas metodi paši sev pierādīja, ka tādu kontroldarbu pasniedzējs nevar uzdot. Viņi sprieda šādi:

"Pierādīsim, ka n-tajā nedēļas dienā no beigām kontroldarbu nevar uzdot (tā kā svētdien lekcijas nenotiek, tad par pirmo dienu no beigām uzskatām sestdienu, par otro- piektdienu utt.".

Bāze. Apgalvojums ir patiess, ja n=1, t.i., kontroldarbu nevar uzdot sestdien. Pieņemsim pretējo, ka pasniedzējs uzdos kontroldarbu sestdien. Tas nozīmē, ka iepriekšējās dienās kontroldarbs netiks uzdots. Tātad piektdienas vakarā mēs jau zināsim, ka pasniedzējs gatavojas uzdot kontroldarbu sestdien. Bet tas ir pretrunā ar apgalvojumu, ka mēs iepriekš nezināsim kontroldarba uzdošanas dienu. Tātad sestdien kontroldarbu uzdot nevar.

Pāreja "<kk". Pieņemsim, ka jau zināms, ka kontroldarbu nevar uzdot nedēļas dienās, kuru numuri no beigām mazāki nekā k.

Pierādīsim, ka kontroldarbu nevar uzdot k-tajā nedēļas dienā no beigām. Pieņemsim pretējo, ka pasniedzējs gatavojas uzdot kontroldarbu k-tajā nedēļas dienā no beigām. Tas nozīmē, ka (k+1)-tajā, (k+2)-tajā, …nedēļas dienā no beigām kontroldarbs netiks uzdots. Tāpēc nedēļas (k+10-ās dienas (no beigām) vakarā mēs jau zināsim, ka kontroldarbs tiks uzdots vai nu k-tajā , vai (k-1)-tajā, …, vai pirmajā nedēļas dienā no beigām. Bet induktīvā hipotēze apgalvo, ka ne (k-1)-tajā, ne (k-2)-tajā, ne pirmajā nedēļas dienā (no beigām) kontroldarbs netiks uzdots. Tātad mēs jau nedēļas (k+1)-tās dienas (no beigām) vakarā zināsim, ka kontroldarbs tiks uzdots k-tajā nedēļas dienā no beigām. Bet tas ir pretrunā ar nosacījumu, ka kontroldarba dienu mēs iepriekš nezināsim. Tātad kontroldarbu nevar uzdot arī k-tajā nedēļas dienā no beigām. Induktīvā pāreja izdarīta."

Studenti kontroldarbam nesagatavojās. Un pēkšņi tršdien pasniedzējs, ienācis auditorijā, plkst. 13.00 uzdeva kontroldarbu, kas studentiem, protams, bija negaidīts- viņi līdz pat kontroldarba uzdošanas brīdim nezināja, ka tas tiks uzdots, jo bija pārliecināti, ka kontroldarbs vispār netiks uzdots. Tādejādi, par spīti studentu pierādījumam, pasniedzējs savu solījumu izpildīja.

Kā tas var būt?

159. Pierādīt 156. uzdevuma apgalvojumu.