Riyazi induksiya

Riyazi induksiya qurmaq üçün adətən istifadə edilən riyazi sübutun metodudur ki, hansi ki, verilən fikir bütün natural ədədlərin (mənfi olmayan tam ədədlər) doğrusudur. Metod daha çox ümumi əsaslandırılmış strukturlar haqqında fikirləri sübut etmək üçün uzana bilər; struktur induksiya kimi tanınan bu ümumiləşdirmədən riyazi məntiqdə və informatikada istifadə edilir. Burada riyazi induksiya rekursiya ilə yaxın əlaqəli olan məna yaratdı. Riyazi induksiya riyaziyyatda qeyri ciddi hesab edilən induktiv mühakimənin forması kimi səhv izah edilməməlidir. Faktiki olaraq, riyazi induksiya ciddi deduktiv mühakimənin formasıdır.

Tarixi

Eramızdan əvvəl 370-də,Platonun ola bilsin ki Parmenidesi aşkar olmayan induktiv sübutun erkən nümunəsini özündə saxlamışdır. Evklidin və Bhaskaranin "dövri metodunda" riyazi induksiyanın ən erkən aşkar olmayan izləri başlanğıcların sayının sonsuz olduğunu göstərmişdi. Bu qədim riyaziyyatçıların heç biri, buna baxmayaraq, induktiv hipotezanı aşkar bəyan etmədi. Başqa oxşar hadisə (zidd olaraq, nə Vacca yazmışdı, necə ki Freudenthal diqqətlə göstərdi), sübut etmək üçün texnikadan istifadə etmiş onun Arithmetiko Libri duetində (1575) Françesko Maurolikodan ki, birinci n tək tam ədədinin məbləği n2-dir. İnduksiyanın prinsipinin birinci qısaca və dürüst ifadə etməsi onun Traitid üçbucağı arifmetikasında (1665) Paskal tərəfindən verildi. Başqa Fransız, Fermat, əlaqəli prinsipin tamamilə kifayət qədər istifadəsini, sonsuz enmə ilə dolayı sübutu etdi. İnduktiv hipotezadan həmçinin İsveçrəli Jakob Bernullidən istifadə etdi və o vaxtdan məşhur oldu. Prinsipin müasir ciddi və sistematik emalı 19-cu əsrdə Corc Boole, Giuseppe Peano ilə və hər şeydən əvvəl Riçard Dedekind ilə gəldi.

Təsvir

Sübut iki addımdan ibarətdir: Əsas: Göstərək ki,n = 0 və ya n = 1-di. İnduktiv addım: Onu göstərək, əgər fikir bəzi n sayısı üçün doğrudusa, onda n + 1 üçün də doğrudur. Bəzi n ədədi üçün saxladığı induktiv addım ehtimal induksiya hipotezası (və ya induktiv hipoteza) adlanır. İnduktiv addımı yerinə yetirmək, bir induksiya hipotezasını güman edir və onda n + 1 üçün fikrini sübut etmək üçün bu ehtimaldan istifadə edilir. Əsasən, n = 0-ın və n = 1-in arasında seçim: 0 təbii say hesab edilir, necə ki, məntiqində n = 0-da ümumidir. Əgər digər tərəfdən, 1 birinci təbii say kimi götürülürse, onda n = 1 olur. Bu metod işləri əvvəl sübut etmək üçün başlanğıc dəyər və sonra sübut etmək üçün doğruluğunun isbatı verilir ki, növbətiyə bir dəyərdən getmək üçün istifadə edilən proses həqiqidir. Bunlarsa, hər ikisi sübut etdi ki, istənilən dəyər dəfələrlə prosesi yerinə yetirmək ilə əldə edilə bilər. Ola bilsin ki, domino effektindən fikirləşmək daha faydalı olar; əgər biri dalbadal (dik vəziyyətdə) dayanan dominoların uzun sırası ilə təqdim edilirsə, əlbəttə ola bilər:

1. Birinci domino düşəcək
2. Nə vaxt ki domino düşür, onun növbəti qonşusu da düşəcək.

Beləliklə, bu nəticəyə gəlirik ki, dominoların hamısı düşəcək və bu fakt qaçılmazdır.

İnduksiyada aksiom

$\forall P.\,[[P(0)\land \forall (k\in \mathbb {N} ).\,[P(k)\Rightarrow P(k+1)]]\Rightarrow \forall (n\in \mathbb {N} ).\,P(n)]$

P hər hansı bir predikat olduğu halda, k və n natural ədədlərdir.

Misallar

Misal 1: Riyazi induksiyanı sübut etmək üçün yazacağım növbəti numunə istənilən n ədədi üçün mümkündür. 0+1+2+...+n = n·(n+1)/2 I pillə: eger n=0 olarsa, 0 = 0·(0+1)/2 —> 0 = 0 —> hansı ki, həqiqətən doğrudur. II pillə: 0+1+2+...+n+n+1 = (n+1)·(n+2)/2 burada,0+1+2+...+n = n·(n+1)/2 yazsaq alarıq ki,

n·(n+1)/2 +n+1 = (n+1)·(n+2)/2 n·(n+1)+2(n+1)/2 = (n+1)·(n+2)/2 (n+2)(n+1)/2 = (n+1)·(n+2)/2 —> hansı ki, doğrudur.bu tam sübutdur.

Misal 2: n≥3 olarsa,n^(n+1) ≥ (n+1)^n tapaq. n·n^n ≥ (n+1)^n n ≥ (n+1/n)^n n ≥ (1+1/n)^n I pillə: eger n=3 olarsa, 3 ≥ (1+1/3)^3 = 64/27 —> 3 ≥ 64/27 —> 64/27 = 2 tam 10/27 3 ≥ 2 —> hansı ki, həqiqətən doğrudur. II pillə: n=k olaraq götürsək, k ≥ (1+1/k)^k n=k+1 götürsək, k+1 ≥ (1+1/k+1)^k+1 burada,k ≥ (1+1/k)^k yazsaq alarıq ki, (1+1 /k+1)^k+1 = (1+ 1/k+1)^k·(1+ 1/k+1)<(1/k+1)^k·(1+1/k+1) ≤ k·(1/k+1) = k+ k/k+1 < k+1 (1+ 1/k+1)^k+1 < k+1 —> sol tərəfi bir az daha sadələşdirsək, (k+1+1/k+1)^k+1 < k+1 (k+2/k+1)^k+1 < 1^k+1 —> qeyd etmek istəyirəm ki,istənilən 1^k+1 həmişə k+1-ə bərabərdi. k+1<k+2 —> k-ları ixtisar etsək, 1<2 —> hansı ki, həqiqətən doğrudur.isbat etdik.

Misal 3: n≥1 olarsa, 1^2 - 2^2 + 3^2 - 4^2 +...+(-1)^n - 1·n^2 = (-1)^n-1·n(n+1)/2 tapaq. I pillə: eger n=1 olarsa, 1^2 = (-1)^0 ·1·2/2 —> 1 = 1 doğrudur. II pillə: n=k olaraq götürsək, 1^2 - 2^2 + 3^2 - 4^2 +...+(-1)^k-1·k^2 = (-1)^k-1·k(k+1)/2 —> {k≥1} n=k+1 götürsək, 1^2 - 2^2 + 3^2 - 4^2 +...+(-1)^k-1·k^2 + (-1)^k·(k+1)^2= (-1)^k·(k+1)·(k+2)/2 —> k+1≥0

                                                                                 —>   k≥0

burada, 1^2 - 2^2 + 3^2 - 4^2 +...+(-1)^k-1·k^2 = (-1)^k-1·k(k+1)/2 alırıq (-1)^k-1·k(k+1)/2 + (-1)^k·(k+1)^2 = (-1)^k·(k+1)(k+2)/2 —> k+1-ləri ixtisar etsək k/2 + (-1)·(k+1) = (-1)·(k+2)/2 k/2 - k-1 = -k-2/2 -k/2 - 1 = -k/2 - 1 —> hansı ki, həqiqətən doğrudur.isbat etdik.