Кіріспе
Математикалық индукция – бұл мәлімдеменің кез келген табиғи сан үшін, яғни шексіз көп жағдайдың барлығының дұрыс екенін дәлелдеу әдісі. Бұл әдіс алдымен қарапайым жағдайды дәлелдеу арқылы жүзеге асырылады, содан кейін егер берілген жағдайдағы талап дұрыс деп қабылданса, келесі жағдай да дұрыс болатынын көрсету арқылы қолданылады. Бұл техниканы түсіндіруге көмектесетін бейресми метафоралар бар, мысалы, доминоның құлауы немесе баспақышпен көтерілу: мәтін = Математикалық индукция біз баспақышпен қалаған биіктікке көтеріле алатынымызды дәлелдейді, төменгі сатыға (негіз) көтеріле алатынымызды және әр сатыдан келесі сатыға (қадамға) көтеріле алатынымызды дәлелдеу арқылы. "Нақты математика", 3-бет. Индукция арқылы дәлелдеу екі жағдайдан тұрады. Біріншісі, негізгі жағдай, басқа жағдайларды білмей, үшін мәлімдемені дәлелдейді. Екінші жағдай, индукциялық қадам, егер мәлімдеме кез келген жағдайда дұрыс болса, онда ол келесі жағдайда да дұрыс болуы керек екенін дәлелдейді. Бұл екі қадам мәлімдеменің кез келген табиғи сан үшін дұрыс екенін анықтайды. Негізгі жағдай міндетті түрде , , , немесе кез келген белгілі бір табиғи санмен басталмайды, бірақ барлық табиғи сандар үшін мәлімдеменің дұрыстығын анықтайды. Бұл әдіс ағаштар сияқты жалпы, жақсы негізделген құрылымдар туралы мәлімдемелерді дәлелдеу үшін кеңейтілуі мүмкін; бұл жалпылау құрылымдық индукция деп аталады және математикалық логикада және компьютерлік ғылымда қолданылады. Математикалық индукция осы кеңейтілген мағынада рекурсиямен тығыз байланысты. Математикалық индукция – формалды дәлелдемелерде қолданылатын қорытындылау ережесі және компьютерлік бағдарламалардың көпшілігі үшін дұрыстығын дәлелдеудің негізі болып табылады. Атына қарамастан, математикалық индукция философияда қолданылатын индуктивті ойлаудан түбегейлі ерекшеленеді, онда көптеген жағдайларды қарастыру ықтимал қорытындыға әкеледі. Математикалық әдіс жалпы мәлімдемені дәлелдеу үшін шексіз көп жағдайларды қарастырады, бірақ оны шексіз көп мәндерді қабылдай алатын айнымалыны қамтитын дедуктивті ойлаудың шекті тізбегі арқылы жасайды. Нәтижесі – бұл мәлімдеменің нақты дәлелі, оның ықтималдығы туралы мәлімдеме емес.
Mathematical induction is a method for proving that a statement is true for every natural number , that is, that the infinitely many cases all hold. This is done by first proving a simple case, then also showing that if we assume the claim is true for a given case, then the next case is also true. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:
text=Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step). |source=Concrete Mathematics, page 3 margins. A proof by induction consists of two cases. The first, the base case, proves the statement for without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case , then it must also hold for the next case These two steps establish that the statement holds for every natural number The base case does not necessarily begin with , but often with , and possibly with any fixed natural number , establishing the truth of the statement for all natural numbers
The method can be extended to prove statements about more general well founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction is an inference rule used in formal proofs, and is the foundation of most correctness proofs for computer programs. Despite its name, mathematical induction differs fundamentally from inductive reasoning as used in philosophy, in which the examination of many cases results in a probable conclusion. The mathematical method examines infinitely many cases to prove a general statement, but it does so by a finite chain of deductive reasoning involving the variable , which can take infinitely many values. The result is a rigorous proof of the statement, not an assertion of its probability.
Мысал: доллар сомаларын монеталар арқылы қалыптастыру
4 және 5 долларлық монеталардың шексіз қоры бар деп есептейік. Индукцияны 12 доллардан үлкен немесе оған тең кез келген соманы осындай монеталардың комбинациясымен құрастыруға болатынын дәлелдеу үшін қолдануға болады. S(k) белгісі «k долларды 4 және 5 долларлық монеталардың комбинациясымен құрастыруға болады» дегенді білдірсін. S(k) барлық k ≥ 12 үшін дұрыс екенін дәлелдеуді индукция арқылы k бойынша келесідей жүзеге асыруға болады:
Базалық жағдай: S(k) k = 12 үшін дұрыс екенін көрсету оңай: үш 4 долларлық монета алыңыз. Индукция қадамы: Егер S(k) k ≥ 12 үшін дұрыс болса (индукция гипотезасы), онда S(k + 1) да дұрыс екенін дәлелдеңіз. S(k) кез келген k ≥ 12 үшін дұрыс деп есептейік. Егер k доллар үшін кем дегенде бір 4 долларлық монета болса, оны 5 долларлық монетамен алмастырып k + 1 доллар жасаңыз. Әйтпесе, егер тек 5 долларлық монеталар қолданылса, k саны 5-ке бөлінуі керек, яғни кем дегенде 15 болуы керек; бірақ онда үш 5 долларлық монетаны төрт 4 долларлық монетамен алмастырып k + 1 доллар жасауға болады. Қай жағдайда болсын, S(k + 1) дұрыс. Демек, индукция принципі бойынша, S(k) барлық k ≥ 12 үшін дұрыс, және дәлелдеу аяқталды. Бұл мысалда, S(k) басқа да мәндер үшін де дұрыс болғанымен, жоғарыдағы дәлелді 12 доллардың ең төмен сомасын кез келген кішірек мәнге өзгертуге болмайды. 1 = m = 11 үшін базалық жағдай жалған; 1 = m = 10 үшін индукция қадамындағы екінші жағдай (үш 5 долларды төрт 4 долларлық монетамен алмастыру) жұмыс істемейді; тіпті одан да кіші m үшін де.
Бірден көп есептегіште индукция
Кейде екі табиғи сан, n және m, туралы мәлімдемені индукция процесін қайталап дәлелдеуге тура келеді. Яғни, n үшін базалық жағдайды және индукциялық қадамды дәлелдейсіз, содан кейін әрқайсысында m үшін базалық жағдайды және индукциялық қадамды дәлелдейсіз. Мысалы, табиғи сандарды қосудың коммутативтілігін дәлелдеуді қараңыз. Үш немесе одан да көп өрнектерді қолданатын күрделірек дәлелдер де мүмкін.
шексіз төмендеу
Шексіз түсу әдісі – Пьер де Ферма қолданған математикалық индукцияның бір түрі. Ол кейбір Q(n) тұжырымының барлық n табиғи сандары үшін жалған екенін көрсетуге қолданылады. Оның дәстүрлі түрі Q(n) тұжырымы белгілі бір n табиғи саны үшін орындалса, онда ол n-ден кіші табиғи сан m үшін де орындалатынын көрсетуден тұрады. Табиғи сандардың шексіз кеміту тізбегі болмайтындықтан, мұндай жағдай мүмкін емес, соның салдарынан (кері дәлелдеу арқылы) Q(n) ешқандай n үшін орындала алмайды.
Осы әдістің дұрыстығын математикалық индукцияның қағидасынан тексеруге болады. "Q(m) тұжырымы n-ден кіші немесе оған тең барлық m табиғи сандары үшін жалған" деп анықталған P(n) тұжырымы бойынша математикалық индукция қолданса, P(n) барлық n үшін орындалады, яғни Q(n) әрбір n табиғи саны үшін жалған.
Толық (күшті) индукция
Толық индукция, мәндер қатары бойынша индукция немесе күшті индукция деп аталатын тағы бір нұсқа (мұндай жағдайда индукцияның негізгі түрі кейде әлсіз индукция деп аталады) күшті гипотеза қолдану арқылы индукция қадамын дәлелдеуді жеңілдетеді: мәлімдеме барлық табиғи сандар үшін дұрыс деген болжаммен дәлелденеді ; керісінше, негізгі форма тек қана деп есептейді. "Күшті индукция" деген атау бұл әдіс "әлсіз индукциядан" гөрі көбірек дәлелдей алады дегенді білдірмейді, тек индукция қадамында қолданылатын күшті гипотезаны көрсетеді. Шындығында, екі әдіс бірдей екенін төменде көрсетілгендей дәлелдеуге болады. Осы толық индукция түрінде негізгі жағдайды , дәлелдеу қажет, және жалпы аргумент қолданылғанға дейін, мысалы, Фибоначчи саны мысалында, қосымша негізгі жағдайларды дәлелдеу қажет болуы мүмкін. Егер жоғарыда сипатталған формада негізгі жағдайды дәлелдеу қажет болмаса, онда барлық үшін (барлық кішірек ) дәлелдеуге болады. Бұл төменде сипатталған трансфинитті индукцияның ерекше жағдайы, бірақ ол енді қалыпты индукциямен тең емес. Бұл формада негізгі жағдай басқа ешқандай болжамсыз дәлелденетін жағдайға біріктіріледі; бұл жағдайды бөлек қарау қажет болуы мүмкін, бірақ кейде бірдей аргумент пен қолданылады, бұл дәлелді қарапайым және әдемі етеді. Алайда, бұл әдісте дәлелдеудің жасырын түрде емес екеніне көз жеткізу өте маңызды, мысалы, "кәдімгіні таңдау" деп айту арқылы немесе m элементтен тұратын жиынның бір элементі бар деп есептеу арқылы.
Although the form just described requires one to prove the base case, this is unnecessary if one can prove (assuming for all lower ) for all This is a special case of transfinite induction as described below, although it is no longer equivalent to ordinary induction. In this form the base case is subsumed by the case , where is proved with no other assumed; this case may need to be handled separately, but sometimes the same argument applies for and , making the proof simpler and more elegant. In this method, however, it is vital to ensure that the proof of does not implicitly assume that , e. g. by saying "choose an arbitrary ", or by assuming that a set of m elements has an element.
Кәдімгі индукцияға теңдестігі
Толық индукция жоғарыда сипатталғандай, қарапайым математикалық индукцияға эквивалентті, яғни бір әдіспен дәлелдеуді екінші әдіспен дәлелдеуге түрлендіруге болады. Толық индукция арқылы дәлелдеу бар деп есептейік. Онда, бұл дәлелді күштірек индукциялық гипотезаны қабылдау арқылы қарапайым индукциялық дәлелге түрлендіруге болады. "барлық үшін " – бұл кәдімгі индукция үшін индукциялық гипотеза болады. Содан кейін, тек қана деп қабылдап, және егер екенін көрсетуге болады. Егер, екінші жағынан, қарапайым индукция арқылы дәлелденсе, онда дәлел толық индукция арқылы да дәлелденген болып табылады: базалық жағдайда ешқандай болжамсыз дәлелденеді, ал индукциялық қадамда барлық алдыңғы жағдайларды қабылдауға болады, бірақ тек қана жағдайын пайдалану жеткілікті.
If, on the other hand, had been proven by ordinary induction, the proof would already effectively be one by complete induction: is proved in the base case, using no assumptions, and is proved in the induction step, in which one may assume all earlier cases but need only use the case .
Мысал: Фибоначчи сандары
Толық индукция бірнеше индукциялық гипотеза мысалдары әрбір индукциялық қадам үшін қажет болғанда ең пайдалы. Мысалы, толық индукцияны n-ші Фибоначчи саны екенін көрсету үшін қолдануға болады, мұнда (алтын қатынас) және көпмүшеліктің түбірлері. әрбір үшін фактысын пайдаланып, жоғарыдағы тепе-теңдік егер олар екі де үшін осы тепе-теңдік орындалады деп есептелсе, тікелей есептеу арқылы тексерілуі мүмкін. Дәлелді аяқтау үшін тепе-теңдік екі базалық жағдайда тексерілуі керек: және .
where is the n th Fibonacci number, and (the golden ratio) and are the roots of the polynomial By using the fact that for each , the identity above can be verified by direct calculation for if one assumes that it already holds for both and To complete the proof, the identity must be verified in the two base cases: and .
Мысал: жай көбейтінділер
Толық индукция арқылы дәлелдеудің тағы бір түрі – мәлімдеме барлық кішірек сандар үшін дұрыс деп есептелетін гипотезаны одан да толық пайдаланады. "1-ден үлкен кез келген табиғи сан (бір немесе бірнеше) жай сандардың көбейтіндісі" деген мәлімдемені қарастырайық, бұл арифметиканың негізгі теоремасының "бар болу" бөлігі. Индукциялық қадамды дәлелдеу үшін индукциялық гипотеза берілген сан үшін барлық кішірек сандар үшін дұрыс екенін білдіреді. Егер сан жай болса, онда ол әрине жай сандардың көбейтіндісі болады, ал егер жай болмаса, онда анықтамасы бойынша көбейтінді болады: , мұнда екі фактордың да бірі 1-ге тең емес; демек, ешқайсысы да тең емес , сондықтан екеуі де 1-ден үлкен және берілген сандан кіші. Индукциялық гипотеза енді және сандарына қолданылады, сондықтан әрқайсысы жай сандардың көбейтіндісі. Осылайша, ол жай сандардың көбейтінділерінің көбейтіндісі, демек, жай сандардың көбейтіндісі болып табылады.
Мысал: қайта қаралған долларлық сомалар
Жоғарыда келтірілген мысалмен, бұл жолы күшті индукция арқылы дәлелдеуге көшеміз. Мәлімдеме сол күйінде қалады:
Дегенмен, дәлелдеу құрылымы мен болжамдарында, кеңейтілген базалық жағдайдан бастап, шағын өзгерістер болады. Дәлел. Базалық жағдай: үшін орындалатынын көрсету. Базалық жағдай орындалады. Индукция қадамы: кез келген берілген үшін, барлық үшін орындалады деп есептейік, сонда орындалатынын дәлелдеу керек. үшін таңдап, және байқап көрсек, индукциялық гипотеза бойынша орындалатыны көрінеді. Яғни, соманы бірнеше доллар және доллар монеталарының комбинациясы арқылы құруға болады. Содан кейін, осы комбинацияға бір доллар монетасын қоссақ, соманы аламыз. Яғни, орындалады. Дәлел келтірілді.
The base case holds. Induction step: Given some , assume holds for all with Prove that holds. Choosing , and observing that shows that holds, by the inductive hypothesis. That is, the sum can be formed by some combination of and dollar coins. Then, simply adding a dollar coin to that combination yields the sum That is, holds Q. E. D.
Алға-артқа индукция
Кейде кері шешіндіру ыңғайлырақ болады, егер ол үшін дұрыс болса, мәлімдемені дәлелдеуге болады. Дегенмен, мәлімдеменің дұрыстығын бір ғана сан үшін дәлелдеу негізгі жағдайды орнату үшін жеткіліксіз; керісінше, мәлімдемені табиғи сандардың шексіз жиыны үшін дәлелдеу қажет. Мысалы, Огюстен Луи Коши алдымен 2-нің барлық дәрежелері үшін арифметикалық және геометриялық орташалардың теңсіздігін дәлелдеу үшін алға (қалыпты) индукцияны қолданды, содан кейін оны барлық табиғи сандар үшін көрсету үшін кері индукцияны қолданды.
inequality of arithmetic and geometric means for all powers of 2, and then used backwards induction to show it for all natural numbers.
Индукциялық қадамдағы қате үлгісі
Индукция қадамы n-нің барлық мәндері үшін дәлелденуі керек. Мұны түсіндіру үшін Джоэл Э. Коэн келесі аргументті ұсынды, ол математикалық индукция арқылы барлық жылқылардың бірдей түсте екенін дәлелдеуге тырысады: Базалық жағдай: тек бір жылқыдан тұратын жиынтықта тек бір ғана түс бар. Индукциялық қадам: кез келген жылқылар жиынында тек бір ғана түс бар деп индукциялық гипотеза ретінде қабылдайық. Енді кез келген жылқылар жиынын қарастырайық. Оларды нөмірлейік: және жиынтықтарын қарастырайық. Әрқайсысы тек жылқыдан тұратын жиынтық болғандықтан, әрқайсысының ішінде тек бір ғана түс бар. Бірақ екі жиынтық бір-бірін қиылыстырады, сондықтан барлық жылқылардың арасында тек бір ғана түс болуы керек. Базалық жағдай тривиальды, ал индукциялық қадам барлық жағдайларда дұрыс. Дегенмен, индукциялық қадамда қолданылатын аргумент , үшін дұрыс емес, өйткені "екі жиынтық қиылысады" деген тұжырым және үшін жалған.
Base case: in a set of only one horse, there is only one color. Induction step: assume as induction hypothesis that within any set of horses, there is only one color. Now look at any set of horses. Number them: Consider the sets and Each is a set of only horses, therefore within each there is only one color. But the two sets overlap, so there must be only one color among all horses. The base case is trivial, and the induction step is correct in all cases However, the argument used in the induction step is incorrect for , because the statement that "the two sets overlap" is false for and .
Кіріспе
(Б. 8.) (Бөлім 1.2.1: Математикалық индукция, 11–21 бб.) (Бөлім 3.8: Трансфинитті индукция, 28–29 бб.)
Тарих
Қайта басылған (CP 3.252–288), (W 4:299–309)