Krótkie podsumowanie metody indukcji matematycznej. Zastosowanie metody indukcji matematycznej do rozwiązywania problemów podzielności liczb naturalnych

Prawdziwa wiedza zawsze opierała się na ustaleniu wzoru i udowodnieniu jego prawdziwości w określonych okolicznościach. Przez tak długi okres istnienia logicznego rozumowania podano sformułowania reguł, a Arystoteles sporządził nawet listę „poprawnych rozumowań”. Historycznie rzecz biorąc, zwyczajem było dzielenie wszystkich wniosków na dwa typy - od konkretnego do wielokrotności (indukcja) i odwrotnie (dedukcja). Należy zauważyć, że rodzaje dowodów od konkretnego do ogólnego i od ogólnego do szczegółowego istnieją tylko w połączeniu i nie mogą być wymieniane.

Indukcja w matematyce

Termin „indukcja” ma korzenie łacińskie i dosłownie tłumaczy się jako „poradnictwo”. Po bliższym przestudiowaniu można wyróżnić strukturę słowa, a mianowicie łaciński przedrostek - in- (oznacza działanie skierowane do wewnątrz lub przebywanie w środku) i -dukcja - wprowadzenie. Warto zauważyć, że istnieją dwa rodzaje - indukcja pełna i niepełna. Pełną formę charakteryzują wnioski wyciągnięte z badań wszystkich obiektów określonej klasy.

Niekompletne - wnioski, które dotyczą wszystkich przedmiotów zajęć, ale wyciągane są na podstawie przestudiowania tylko niektórych jednostek.

Pełna indukcja matematyczna to wnioskowanie oparte na ogólnym wniosku o całej klasie dowolnych obiektów, które są funkcjonalnie połączone relacjami naturalnego ciągu liczb, oparte na znajomości tego związku funkcjonalnego. W tym przypadku proces sprawdzający przebiega w trzech etapach:

pierwsza dowodzi słuszności stanowiska indukcji matematycznej. Przykład: f = 1, indukcja;
kolejny etap opiera się na założeniu, że stanowisko obowiązuje dla wszystkich liczb naturalnych. Oznacza to, że f=h jest hipotezą indukcyjną;
w trzecim etapie dowodzi się słuszności stanowiska dla liczby f=h+1 w oparciu o poprawność położenia punktu poprzedniego – jest to przejście indukcyjne, czyli krok indukcji matematycznej. Przykładem jest tzw. jeśli spadnie pierwszy kamień w rzędzie (podstawa), to wszystkie kamienie w rzędzie spadną (przejście).

I żartobliwie i poważnie

Dla łatwiejszego zrozumienia przykłady rozwiązań wykorzystujących metodę indukcji matematycznej przedstawiono w formie zadań żartobliwych. Oto zadanie „Uprzejmy kolejka”:

Zasady postępowania zabraniają mężczyźnie skręcania przed kobietą (w takiej sytuacji może ona iść dalej). Bazując na tym stwierdzeniu, jeśli ostatni w kolejce jest mężczyzną, to wszyscy pozostali są mężczyznami.

Uderzającym przykładem metody indukcji matematycznej jest problem „lotu bezwymiarowego”:

Wymagane jest wykazanie, że w minibusie zmieści się dowolna liczba osób. Prawdą jest, że w pojeździe bez problemu zmieści się jedna osoba (podstawa). Ale niezależnie od tego, jak zapełniony jest minibus, zawsze zmieści się w nim 1 pasażer (stopień indukcyjny).

Znane kręgi

Przykłady rozwiązywania problemów i równań metodą indukcji matematycznej są dość powszechne. Jako ilustrację tego podejścia rozważmy następujący problem.

Stan: na płaszczyźnie znajduje się h okręgów. Należy wykazać, że dla dowolnego układu figur, utworzoną przez nie mapę można poprawnie pokolorować dwoma kolorami.

Rozwiązanie: gdy h=1 prawdziwość twierdzenia jest oczywista, zatem dowód zostanie skonstruowany dla liczby okręgów h+1.

Załóżmy, że stwierdzenie to obowiązuje dla dowolnej mapy i na płaszczyźnie znajdują się okręgi h+1. Usuwając jedno z okręgów z sumy, możesz otrzymać mapę poprawnie pokolorowaną dwoma kolorami (czarnym i białym).

Podczas przywracania usuniętego okręgu kolor każdego obszaru zmienia się na przeciwny (w tym przypadku wewnątrz okręgu). Rezultatem jest mapa poprawnie pokolorowana w dwóch kolorach, co należało sprawdzić.

Przykłady z liczbami naturalnymi

Poniżej wyraźnie pokazano zastosowanie metody indukcji matematycznej.

Przykłady rozwiązań:

Udowodnić, że dla dowolnego h poprawna jest równość:

1 2 +2 2 +3 2 +…+h 2 =h(h+1)(2h+1)/6.

1. Niech h=1, co oznacza:

R 1 =1 2 =1(1+1)(2+1)/6=1

Wynika z tego, że dla h=1 stwierdzenie jest prawdziwe.

2. Zakładając, że h=d otrzymujemy równanie:

R1 =d2 =d(d+1)(2d+1)/6=1

3. Zakładając, że h=d+1 okazuje się, że:

R d+1 =(d+1) (d+2) (2d+3)/6

R d+1 = 1 2 +2 2 +3 2 +…+d 2 +(d+1) 2 = d(d+1)(2d+1)/6+ (d+1) 2 =(d( d+1)(2d+1)+6(d+1) 2)/6=(d+1)(d(2d+1)+6(k+1))/6=

(d+1)(2d 2 +7d+6)/6=(d+1)(2(d+3/2)(d+2))/6=(d+1)(d+2)( 2d+3)/6.

W ten sposób udowodniono słuszność równości dla h=d+1, zatem twierdzenie jest prawdziwe dla dowolnej liczby naturalnej, co pokazano na przykładowym rozwiązaniu metodą indukcji matematycznej.

Zadanie

Stan: wymagany jest dowód, że dla dowolnej wartości h wyrażenie 7 h -1 jest podzielne przez 6 bez reszty.

Rozwiązanie:

1. Powiedzmy, że h=1, w tym przypadku:

R 1 =7 1 -1=6 (tj. podzielone przez 6 bez reszty)

Zatem dla h=1 stwierdzenie jest prawdziwe;

2. Niech h=d i 7 d -1 podzielimy przez 6 bez reszty;

3. Dowodem słuszności twierdzenia dla h=d+1 jest wzór:

R re +1 =7 d +1 -1=7∙7 d -7+6=7(7 d -1)+6

W tym przypadku pierwszy wyraz jest podzielny przez 6 zgodnie z założeniem pierwszego punktu, a drugi wyraz jest równy 6. Prawdziwe jest stwierdzenie, że 7 h -1 dzieli się przez 6 bez reszty dla dowolnego naturalnego h jest prawdziwe.

Błędy w ocenie

Często w dowodach stosuje się błędne rozumowanie ze względu na niedokładność zastosowanych konstrukcji logicznych. Dzieje się tak głównie wtedy, gdy naruszona zostaje struktura i logika dowodu. Przykładem błędnego rozumowania jest poniższa ilustracja.

Zadanie

Stan: wymagany jest dowód, że stos kamieni nie jest stosem.

Rozwiązanie:

1. Załóżmy, że h=1, w tym przypadku w stosie znajduje się 1 kamień i stwierdzenie jest prawdziwe (podstawa);

2. Niech dla h=d prawdą będzie, że stos kamieni nie jest stosem (założenie);

3. Niech h=d+1, z czego wynika, że po dodaniu jeszcze jednego kamienia zbiór nie będzie kupą. Wniosek sam w sobie sugeruje, że założenie jest ważne dla wszystkich naturalnych h.

Błąd polega na tym, że nie ma definicji, ile kamieni tworzy stos. Takie pominięcie nazywa się pochopnym uogólnieniem metody indukcji matematycznej. Przykład pokazuje to wyraźnie.

Indukcja i prawa logiki

Historycznie rzecz biorąc, zawsze „idą ramię w ramię”. Dyscypliny naukowe, takie jak logika i filozofia, opisują je w formie przeciwieństw.

Z punktu widzenia prawa logiki definicje indukcyjne opierają się na faktach, a prawdziwość przesłanek nie przesądza o poprawności wynikowego stwierdzenia. Często wnioski uzyskuje się z pewnym stopniem prawdopodobieństwa i wiarygodności, co oczywiście należy zweryfikować i potwierdzić dodatkowymi badaniami. Przykładem indukcji w logice może być następujące stwierdzenie:

W Estonii jest susza, susza na Łotwie, susza na Litwie.

Estonia, Łotwa i Litwa to kraje bałtyckie. We wszystkich krajach bałtyckich panuje susza.

Z przykładu możemy wywnioskować, że metodą indukcji nie da się uzyskać nowych informacji czy prawdy. Jedyne, na co można liczyć, to pewna prawdziwość wniosków. Co więcej, prawdziwość przesłanek nie gwarantuje takich samych wniosków. Nie oznacza to jednak, że indukcja schodzi na margines dedukcji: ogromną liczbę przepisów i praw naukowych uzasadnia się metodą indukcyjną. Przykładem jest ta sama matematyka, biologia i inne nauki. Wynika to głównie z metody indukcji całkowitej, choć w niektórych przypadkach ma zastosowanie również indukcja częściowa.

Czcigodny wiek indukcji pozwolił jej przeniknąć do prawie wszystkich sfer ludzkiej działalności - jest to nauka, ekonomia i codzienne wnioski.

Indukcja w środowisku naukowym

Metoda indukcyjna wymaga skrupulatnego podejścia, ponieważ zbyt wiele zależy od liczby badanych części całości: im większa liczba badanych, tym bardziej wiarygodny wynik. W oparciu o tę cechę prawa naukowe uzyskane metodą indukcji są przez długi czas testowane na poziomie założeń probabilistycznych w celu wyodrębnienia i zbadania wszystkich możliwych elementów strukturalnych, połączeń i wpływów.

W nauce wniosek indukcyjny opiera się na istotnych cechach, z wyjątkiem przypadkowych zapisów. Fakt ten jest istotny w związku ze specyfiką wiedzy naukowej. Widać to wyraźnie na przykładach indukcji w nauce.

W świecie naukowym wyróżnia się dwa rodzaje indukcji (w związku ze sposobem studiowania):

selekcja indukcyjna (lub selekcja);
indukcja - wykluczenie (eliminacja).

Pierwszy typ wyróżnia się metodycznym (skrupulatnym) doborem próbek klasy (podklas) z różnych jej obszarów.

Przykładem tego typu indukcji jest: srebro (lub jego sole) oczyszcza wodę. Wniosek opiera się na wieloletnich obserwacjach (rodzaj selekcji potwierdzeń i obaleń – selekcji).

Drugi rodzaj indukcji opiera się na wnioskach ustalających związki przyczynowe i wykluczających okoliczności, które nie odpowiadają jej właściwościom, a mianowicie powszechność, przestrzeganie kolejności czasowej, konieczność i jednoznaczność.

Indukcja i dedukcja ze stanowiska filozofii

Patrząc wstecz, termin indukcja został po raz pierwszy wspomniany przez Sokratesa. Arystoteles opisał przykłady indukcji w filozofii w bardziej przybliżonym słowniku terminologicznym, jednak kwestia indukcji niepełnej pozostaje otwarta. Po prześladowaniu sylogizmu arystotelesowskiego metodę indukcyjną zaczęto uznawać za owocną i jedyną możliwą w naukach przyrodniczych. Bacon uważany jest za ojca indukcji jako niezależnej metody specjalnej, nie udało mu się jednak oddzielić indukcji od metody dedukcyjnej, jak tego domagali się jego współcześni.

Indukcję rozwinął dalej J. Mill, który rozważał teorię indukcyjną z perspektywy czterech głównych metod: zgodności, różnicy, reszt i odpowiadających im zmian. Nic dziwnego, że dziś wymienione metody, szczegółowo zbadane, mają charakter dedukcyjny.

Uświadomienie sobie niespójności teorii Bacona i Milla skłoniło naukowców do zbadania probabilistycznych podstaw indukcji. Jednak i tutaj istniały pewne skrajności: próbowano zredukować indukcję do teorii prawdopodobieństwa ze wszystkimi wynikającymi z tego konsekwencjami.

Indukcja otrzymuje wotum zaufania dzięki praktycznemu zastosowaniu w niektórych obszarach tematycznych i dzięki dokładności metrycznej podstawy indukcyjnej. Przykładem indukcji i dedukcji w filozofii można uznać Prawo Powszechnego Grawitacji. W dniu odkrycia prawa Newtonowi udało się je zweryfikować z dokładnością do 4%. A sprawdzane ponad dwieście lat później, poprawność została potwierdzona z dokładnością do 0,0001 procent, chociaż weryfikację przeprowadzono na podstawie tych samych uogólnień indukcyjnych.

Współczesna filozofia większą wagę przywiązuje do dedukcji, która podyktowana jest logiczną chęcią wyciągnięcia nowej wiedzy (lub prawd) z tego, co już znane, bez uciekania się do doświadczenia i intuicji, ale przy użyciu „czystego” rozumowania. Odnosząc się do prawdziwych przesłanek w metodzie dedukcyjnej, we wszystkich przypadkach wynikiem jest stwierdzenie prawdziwe.

Ta bardzo ważna cecha nie powinna przyćmiewać wartości metody indukcyjnej. Indukcja bowiem, bazując na dorobku doświadczenia, staje się także środkiem jego przetwarzania (w tym uogólniania i systematyzacji).

Zastosowanie indukcji w ekonomii

Indukcja i dedukcja są od dawna stosowane jako metody badania gospodarki i prognozowania jej rozwoju.

Zakres zastosowania metody indukcyjnej jest dość szeroki: badanie spełnienia wskaźników prognozowanych (zyski, amortyzacja itp.) oraz ogólna ocena stanu przedsiębiorstwa; kształtowanie skutecznej polityki promocji przedsiębiorstwa opartej na faktach i ich relacjach.

Tę samą metodę indukcji zastosowano w „Mapach Shewharta”, gdzie przy założeniu podziału procesów na kontrolowane i niesterowane stwierdza się, że szkielet procesu kontrolowanego jest nieaktywny.

Należy zaznaczyć, że prawa nauki uzasadnia się i potwierdza za pomocą metody indukcji, a ponieważ ekonomia jest nauką, która często wykorzystuje analizę matematyczną, teorię ryzyka i statystykę, wcale nie dziwi fakt, że indukcja znajduje się na liście głównych metod.

Przykładem indukcji i dedukcji w ekonomii jest następująca sytuacja. Wzrost cen żywności (z koszyka konsumenckiego) i dóbr pierwszej potrzeby skłania konsumenta do myślenia o pojawiających się wysokich kosztach w państwie (indukcja). Jednocześnie z faktu wysokich cen można, wykorzystując metody matematyczne, wyprowadzić wskaźniki wzrostu cen dla poszczególnych towarów lub kategorii towarów (odliczenie).

Najczęściej kadra kierownicza, menedżerowie i ekonomiści sięgają po metodę indukcyjną. Aby móc z wystarczającą prawdziwością przewidzieć rozwój przedsiębiorstwa, zachowania rynku i skutki konkurencji, konieczne jest indukcyjno-dedukcyjne podejście do analizy i przetwarzania informacji.

Wyraźny przykład indukcji w ekonomii związanej z błędnymi sądami:

zysk spółki spadł o 30%;
firma konkurencyjna rozszerzyła swoją linię produktów;
nic więcej się nie zmieniło;
polityka produkcyjna konkurencyjnej firmy spowodowała zmniejszenie zysków o 30%;
dlatego należy wdrożyć tę samą politykę produkcyjną.

Przykład jest barwną ilustracją tego, jak nieudolne zastosowanie metody indukcyjnej przyczynia się do ruiny przedsiębiorstwa.

Dedukcja i indukcja w psychologii

Skoro istnieje metoda, to logicznie rzecz biorąc, istnieje również odpowiednio zorganizowane myślenie (aby zastosować metodę). Psychologia jako nauka badająca procesy psychiczne, ich powstawanie, rozwój, relacje, interakcje, zwraca uwagę na myślenie „dedukcyjne”, jako jedną z form przejawu dedukcji i indukcji. Niestety na stronach poświęconych psychologii w Internecie praktycznie nie ma uzasadnienia dla integralności metody dedukcyjno-indukcyjnej. Chociaż profesjonalni psychologowie częściej spotykają się z przejawami indukcji, a raczej błędnymi wnioskami.

Przykładem indukcji w psychologii, jako ilustracja błędnych sądów, jest stwierdzenie: moja matka oszukuje, zatem wszystkie kobiety są oszustami. Możesz znaleźć jeszcze bardziej „błędne” przykłady indukcji z życia:

uczeń jest niezdolny do niczego, jeśli dostanie złą ocenę z matematyki;
on jest głupcem;
jest mądry;
Mogę zrobić wszystko;

Oraz wiele innych sądów wartościujących opartych na całkowicie przypadkowych i czasami nieistotnych przesłankach.

Należy zauważyć: kiedy błędny osąd danej osoby osiąga poziom absurdu, dla psychoterapeuty pojawia się granica pracy. Przykład wprowadzenia na wizytę specjalistyczną:

„Pacjent ma całkowitą pewność, że kolor czerwony jest dla niego niebezpieczny tylko w jakiejkolwiek formie. W rezultacie osoba wykluczyła tę kolorystykę ze swojego życia - w jak największym stopniu. Możliwości komfortowego pobytu w domu jest wiele. Możesz odrzucić wszystkie czerwone przedmioty lub zastąpić je analogami wykonanymi w innej kolorystyce. Ale w miejscach publicznych, w pracy, w sklepie - to niemożliwe. Kiedy pacjent znajduje się w sytuacji stresowej, za każdym razem doświadcza „przypływu” zupełnie innych stanów emocjonalnych, które mogą stanowić zagrożenie dla innych.

Ten przykład indukcji i nieświadomej indukcji nazywany jest „utrwalonymi ideami”. Jeśli przydarzy się to osobie zdrowej psychicznie, możemy mówić o braku organizacji aktywności umysłowej. Sposobem na pozbycie się stanów obsesyjnych może być elementarny rozwój myślenia dedukcyjnego. W innych przypadkach psychiatrzy pracują z takimi pacjentami.

Powyższe przykłady indukcji wskazują, że „nieznajomość prawa nie zwalnia od konsekwencji (błędnych sądów)”.

Psychologowie pracujący nad myśleniem dedukcyjnym opracowali listę zaleceń, które mają pomóc ludziom opanować tę metodę.

Punkt pierwszy to rozwiązywanie problemów. Jak widać, formę indukcji stosowaną w matematyce można uznać za „klasyczną”, a zastosowanie tej metody przyczynia się do „dyscypliny” umysłu.

Kolejnym warunkiem rozwoju myślenia dedukcyjnego jest poszerzanie horyzontów (ci, którzy myślą jasno, wyrażają się jasno). Zalecenie to kieruje „cierpienie” do skarbnic nauki i informacji (biblioteki, strony internetowe, inicjatywy edukacyjne, podróże itp.).

Na szczególną uwagę zasługuje tzw. „indukcja psychologiczna”. Termin ten, choć nieczęsto, można spotkać w Internecie. Żadne źródła nie podają choćby krótkiego sformułowania definicji tego terminu, lecz powołują się na „przykłady z życia”, podając jako nowy rodzaj indukcji albo sugestię, albo pewne formy choroby psychicznej, albo skrajne stany psychiczne. ludzka psychika. Z powyższego jasno wynika, że próba wyprowadzenia „nowego terminu” w oparciu o fałszywe (często nieprawdziwe) przesłanki skazuje eksperymentatora na uzyskanie błędnego (lub pochopnego) stwierdzenia.

Należy zaznaczyć, że nawiązanie do eksperymentów z 1960 roku (bez wskazania miejsca, nazwisk eksperymentatorów, próby badawczej i przede wszystkim celu eksperymentu) wygląda, delikatnie mówiąc, nieprzekonująco, a Stwierdzenie, że mózg odbiera informacje z pominięciem wszystkich narządów percepcji (w tym przypadku sformułowanie „jest dotknięty” pasowałoby bardziej organicznie), każe pomyśleć o łatwowierności i bezkrytyczności autora stwierdzenia.

Zamiast wniosków

Nie bez powodu królowa nauk, matematyka, wykorzystuje wszystkie możliwe rezerwy metody indukcji i dedukcji. Rozważane przykłady pozwalają stwierdzić, że powierzchowne i nieudolne (jak to się mówi bezmyślne) stosowanie nawet najbardziej dokładnych i niezawodnych metod zawsze prowadzi do błędnych wyników.

W świadomości masowej metoda dedukcji kojarzona jest ze słynnym Sherlockiem Holmesem, który w swoich konstrukcjach logicznych coraz częściej posługuje się przykładami indukcji, stosując dedukcję w odpowiednich sytuacjach.

W artykule zbadano przykłady zastosowania tych metod w różnych naukach i sferach działalności człowieka.

METODA INDUKCJI MATEMATYCZNEJ

Słowo indukcja w języku rosyjskim oznacza wskazówki, a wnioski oparte na obserwacjach, eksperymentach, tj. nazywane są indukcyjnymi. uzyskane przez wnioskowanie od szczegółu do ogółu.

Na przykład każdego dnia obserwujemy, że Słońce wschodzi ze wschodu. Dlatego możesz być pewien, że jutro pojawi się na wschodzie, a nie na zachodzie. Wyciągamy ten wniosek bez uciekania się do jakichkolwiek założeń na temat przyczyny ruchu Słońca po niebie (co więcej, sam ten ruch okazuje się oczywisty, ponieważ kula ziemska faktycznie się porusza). A jednak ten indukcyjny wniosek poprawnie opisuje obserwacje, które poczynimy jutro.

Rola wniosków indukcyjnych w naukach eksperymentalnych jest bardzo duża. Podają te przepisy, z których następnie w drodze dedukcji wyciąga się dalsze wnioski. I chociaż mechanika teoretyczna opiera się na trzech zasadach ruchu Newtona, to same prawa były wynikiem głębokiego przemyślenia danych eksperymentalnych, w szczególności praw ruchu planet Keplera, które wyprowadził z przetwarzania wieloletnich obserwacji duńskiego astronoma Tycho Brawo. Obserwacja i indukcja okazują się przydatne w przyszłości do wyjaśnienia przyjętych założeń. Po eksperymentach Michelsona nad pomiarem prędkości światła w ośrodku ruchomym konieczne okazało się wyjaśnienie praw fizyki i stworzenie teorii względności.

W matematyce rola indukcji polega w dużej mierze na tym, że leży ona u podstaw wybranych aksjomatyk. Kiedy wieloletnia praktyka pokazała, że droga prosta jest zawsze krótsza od krzywej lub łamanej, naturalnym było sformułowanie aksjomatu: dla dowolnych trzech punktów A, B i C nierówność

Koncepcja podążania, będąca podstawą arytmetyki, pojawiła się także z obserwacji formacji żołnierzy, statków i innych uporządkowanych zbiorów.

Nie należy jednak sądzić, że na tym wyczerpuje się rola indukcji w matematyce. Oczywiście nie powinniśmy eksperymentalnie testować twierdzeń wydedukowanych logicznie z aksjomatów: jeśli podczas wyprowadzania nie popełniono błędów logicznych, to są one prawdziwe o tyle, o ile przyjęte przez nas aksjomaty są prawdziwe. Z tego systemu aksjomatów można jednak wywnioskować wiele twierdzeń. Wybór tych twierdzeń, które należy udowodnić, ponownie sugeruje indukcja. To właśnie pozwala oddzielić twierdzenia przydatne od bezużytecznych, wskazuje, które twierdzenia mogą okazać się prawdziwe, a nawet pomaga nakreślić ścieżkę dowodu.

Istota metody indukcji matematycznej

W wielu gałęziach arytmetyki, algebry, geometrii i analizy konieczne jest udowodnienie prawdziwości zdań A(n) w zależności od zmiennej naturalnej. Dowód prawdziwości twierdzenia A(n) dla wszystkich wartości zmiennej często można przeprowadzić metodą indukcji matematycznej, która opiera się na następującej zasadzie.

Twierdzenie A(n) uważa się za prawdziwe dla wszystkich naturalnych wartości zmiennej, jeżeli spełnione są dwa poniższe warunki:

Twierdzenie A(n) jest prawdziwe dla n=1.

Z założenia, że A(n) jest prawdziwe dla n=k (gdzie k jest dowolną liczbą naturalną), wynika, że jest to prawdziwe dla kolejnej wartości n=k+1.

Zasada ta nazywana jest zasadą indukcji matematycznej. Zwykle jest on wybierany jako jeden z aksjomatów definiujących naturalny ciąg liczb i dlatego jest akceptowany bez dowodu.

Metoda indukcji matematycznej oznacza następującą metodę dowodu. Jeżeli chcesz udowodnić prawdziwość zdania A(n) dla wszystkich naturalnych n, to w pierwszej kolejności należy sprawdzić prawdziwość zdania A(1), a w drugiej kolejności założyć prawdziwość zdania A(k), spróbuj udowodnić, że stwierdzenie A(k +1) jest prawdziwe. Jeśli można to udowodnić, a dowód pozostaje ważny dla każdej naturalnej wartości k, wówczas zgodnie z zasadą indukcji matematycznej zdanie A(n) uznaje się za prawdziwe dla wszystkich wartości n.

Metoda indukcji matematycznej jest szeroko stosowana w dowodzie twierdzeń, tożsamości, nierówności, w rozwiązywaniu problemów podzielności, w rozwiązywaniu niektórych problemów geometrycznych i wielu innych.

Metoda indukcji matematycznej w rozwiązywaniu problemów

podzielność

Stosując metodę indukcji matematycznej można udowodnić różne twierdzenia dotyczące podzielności liczb naturalnych.

Poniższe stwierdzenie można udowodnić stosunkowo prosto. Pokażmy, jak to uzyskać, stosując metodę indukcji matematycznej.

Przykład 1. Jeśli n jest liczbą naturalną, to jest to liczba parzysta.

Gdy n=1 prawdziwe jest nasze stwierdzenie: - liczba parzysta. Załóżmy, że jest to liczba parzysta. Ponieważ 2k jest liczbą parzystą nawet. Zatem parzystość zostaje udowodniona dla n=1, a parzystość jest wywnioskowana z parzystości Oznacza to, że jest to parzyste dla wszystkich naturalnych wartości n.

Przykład 2.Udowodnij prawdziwość zdania

A(n)=(liczba 5 jest wielokrotnością 19), n jest liczbą naturalną.

Rozwiązanie.

Stwierdzenie A(1)=(liczba podzielna przez 19) jest prawdziwe.

Załóżmy, że dla pewnej wartości n=k

A(k)=(liczba podzielna przez 19) jest prawdziwa. Potem, od

Oczywiście, A(k+1) jest również prawdziwe. Rzeczywiście, pierwszy wyraz jest podzielny przez 19 ze względu na założenie, że A(k) jest prawdziwe; drugi wyraz jest również podzielny przez 19, ponieważ zawiera współczynnik 19. Oba warunki zasady indukcji matematycznej są spełnione, dlatego twierdzenie A(n) jest prawdziwe dla wszystkich wartości n.

Zastosowanie metody indukcji matematycznej do

seria podsumowująca

Przykład 1.Udowodnić formułę

, n jest liczbą naturalną.

Rozwiązanie.

Gdy n=1, obie strony równości zwracają się do jedynki, a zatem pierwszy warunek zasady indukcji matematycznej jest spełniony.

Załóżmy, że wzór jest poprawny dla n=k, tj.

Dodajmy obie strony tej równości i przekształćmy prawą stronę. Wtedy otrzymamy

Zatem z faktu, że wzór jest prawdziwy dla n=k wynika, że jest on prawdziwy także dla n=k+1. To stwierdzenie jest prawdziwe dla dowolnej wartości naturalnej k . Zatem drugi warunek zasady indukcji matematycznej jest również spełniony. Formuła jest sprawdzona.

Przykład 2.Udowodnić, że suma pierwszych n liczb ciągu naturalnego jest równa .

Rozwiązanie.

Oznaczmy wymaganą kwotę, tj. .

Gdy n=1 hipoteza jest prawdziwa.

Pozwalać . Pokażmy to .

Rzeczywiście,

Problem jest rozwiązany.

Przykład 3.Udowodnić, że suma kwadratów pierwszych n liczb ciągu naturalnego jest równa .

Rozwiązanie.

Pozwalać .

Udawajmy, że . Następnie

I w końcu.

Przykład 4. Udowodnij to .

Rozwiązanie.

Jeśli następnie

Przykład 5. Udowodnij to

Rozwiązanie.

Gdy n=1 hipoteza jest oczywiście prawdziwa.

Pozwalać .

Udowodnijmy to.

Naprawdę,

Przykłady zastosowania metody indukcji matematycznej

dowód nierówności

Przykład 1.Udowodnić, że dla dowolnej liczby naturalnej n>1

Rozwiązanie.

Oznaczmy lewą stronę nierówności przez .

Zatem dla n=2 nierówność jest prawdziwa.

Niech dla jakiegoś k. Udowodnijmy, że wtedy i . Mamy , .

Porównując i , mamy , tj. .

Dla dowolnej dodatniej liczby całkowitej k prawa strona ostatniej równości jest dodatnia. Dlatego . Ale to oznacza także.

Przykład 2.Znajdź błąd w rozumowaniu.

Oświadczenie. Dla dowolnej liczby naturalnej n nierówność jest prawdziwa.

Dowód.

. (1)

Udowodnijmy, że wtedy nierówność obowiązuje także dla n=k+1, tj.

Rzeczywiście, nie mniej niż 2 dla dowolnego naturalnego k. Dodajmy do lewej strony nierówności (1) i do prawej strony 2. Otrzymujemy dobrą nierówność, czyli . Stwierdzenie zostało udowodnione.

Przykład 3.Udowodnij to , gdzie >-1, , n jest liczbą naturalną większą niż 1.

Rozwiązanie.

Dla n=2 nierówność jest prawdziwa, ponieważ .

Niech nierówność będzie prawdziwa dla n=k, gdzie k jest liczbą naturalną, tj.

. (1)

Pokażmy, że wtedy nierówność obowiązuje także dla n=k+1, tj.

. (2)

Rzeczywiście, pod warunkiem, , zatem nierówność jest prawdziwa

, (3)

otrzymane z nierówności (1) poprzez pomnożenie każdej części przez . Zapiszmy nierówność (3) następująco: . Odrzucając człon dodatni po prawej stronie ostatniej nierówności, otrzymujemy nierówność zadowalającą (2).

Przykład 4. Udowodnij to

(1)

gdzie , , n jest liczbą naturalną większą niż 1.

Rozwiązanie.

Dla n=2 nierówność (1) przyjmuje postać

. (2)

Ponieważ , to nierówność jest prawdziwa

. (3)

Dodając do każdej części nierówności (3) otrzymujemy nierówność (2).

Dowodzi to, że dla n=2 prawdziwa jest nierówność (1).

Niech nierówność (1) będzie prawdziwa dla n=k, gdzie k jest liczbą naturalną, tj.

. (4)

Udowodnijmy, że wówczas nierówność (1) musi być prawdziwa także dla n=k+1, czyli:

(5)

Pomnóżmy obie strony nierówności (4) przez a+b. Ponieważ pod warunkiem , otrzymujemy następującą nierówność uczciwą:

. (6)

Aby udowodnić zasadność nierówności (5), wystarczy to wykazać

, (7)

lub, co jest takie samo,

. (8)

Nierówność (8) jest równoważna nierówności

. (9)

Jeżeli , to i po lewej stronie nierówności (9) mamy iloczyn dwóch liczb dodatnich. Jeżeli , to i po lewej stronie nierówności (9) mamy iloczyn dwóch liczb ujemnych. W obu przypadkach prawdziwa jest nierówność (9).

Dowodzi to, że z ważności nierówności (1) dla n=k wynika jej ważność dla n=k+1.

Metoda indukcji matematycznej stosowana do innych

zadania

Najbardziej naturalnym zastosowaniem metody indukcji matematycznej w geometrii, bliskim zastosowaniu tej metody w teorii liczb i algebrze, jest jej zastosowanie do rozwiązywania problemów obliczeń geometrycznych. Spójrzmy na kilka przykładów.

Przykład 1.Oblicz bok kwadratu foremnego wpisanego w okrąg o promieniu R.

Rozwiązanie.

Gdy n=2 jest poprawne 2 N - kwadrat jest kwadratem; jego strona. Dalej, zgodnie ze wzorem na podwojenie

stwierdzamy, że bok foremnego ośmiokąta , bok sześciokąta foremnego , bok regularnego trójkąta trzydziestu dwóch . Możemy zatem założyć, że bok prawidłowego wpisanego 2 N - kwadrat dla dowolnej równości

. (1)

Załóżmy, że bok kwadratu wpisanego foremnego wyraża się wzorem (1). W tym przypadku zgodnie ze wzorem na podwojenie

skąd wynika, że wzór (1) obowiązuje dla wszystkich n.

Przykład 2.Na ile trójkątów można podzielić n-gon (niekoniecznie wypukły) za pomocą rozłącznych przekątnych?

Rozwiązanie.

W przypadku trójkąta liczba ta jest równa jeden (w trójkącie nie można narysować ani jednej przekątnej); dla czworoboku liczba ta wynosi oczywiście dwa.

Załóżmy, że wiemy już, że każdy k-gon, gdzie k 1 A 2 ...A n w trójkąty.

Jakiś

A 1 A 2

Niech A 1 A k będzie jedną z przekątnych tego podziału; dzieli n-gon A 1 A 2 ...A n na k-gon A 1 A 2 ...A k i (n-k+2)-gon A 1 A k A k+1 .. .Jakiś . Z przyjętego założenia wynika, że całkowita liczba trójkątów w przegrodzie będzie równa

(k-2)+[(n-k+2)-2]=n-2;

Zatem nasze twierdzenie jest udowodnione dla wszystkich n.

Przykład 3.Podaj regułę obliczania liczby P(n) sposobów, na jakie wypukły n-kąt można podzielić na trójkąty za pomocą rozłącznych przekątnych.

Rozwiązanie.

Dla trójkąta liczba ta jest oczywiście równa jeden: P(3)=1.

Załóżmy, że wyznaczyliśmy już liczby P(k) dla wszystkich k 1 A 2 ...A n . Ilekroć dzieli się go na trójkąty, bok A 1A2 będzie bokiem jednego z trójkątów podziału, trzeci wierzchołek tego trójkąta może pokrywać się z każdym z punktów A 3, A 4, …, An n . Liczba sposobów podziału n-kąta, na który ten wierzchołek pokrywa się z punktem A 3 , jest równa liczbie sposobów podziału (n-1)-kątu A na trójkąty 1 A 3 A 4 …A n , tj. równa się P(n-1). Liczba metod partycjonowania, w których ten wierzchołek pokrywa się z A 4 , jest równe liczbie sposobów podziału (n-2)-kątu A 1 A 4 A 5 …A n , tj. równa się P(n-2)=P(n-2)P(3); liczba metod podziału, w których pokrywa się z A 5 , jest równe P(n-3)P(4), ponieważ każdy z podziałów (n-3)-gon A 1 A 5 ...A n można łączyć z każdą z przegród czworoboku A 2 za 3 za 4 za 5 itp. W ten sposób dochodzimy do następującej zależności:

Р(n)=P(n-1)+P(n-2)P(3)+P(n-3)P(4)+…+P(3)P(n-2)+P(n -1).

Stosując ten wzór konsekwentnie otrzymujemy:

P(4)=P(3)+P(3)=2,

P(5)=P(4)+P(3)P(3)+P(4)+5,

P(6)=P(5)+P(4)P(3)+P(3)P(4)+P(5)=14

itp.

Zadania z wykresami można rozwiązywać także metodą indukcji matematycznej.

Niech na płaszczyźnie będzie sieć linii, które łączą pewne punkty i nie mają innych punktów. Taką sieć linii nazwiemy mapą, biorąc pod uwagę punkty jako jej wierzchołki, odcinki krzywych pomiędzy dwoma sąsiednimi wierzchołkami - granice mapy, części płaszczyzny, na które jest ona podzielona granicami - kraje mapy.

Niech w samolocie zostanie podana jakaś mapa. Powiemy, że jest poprawnie pokolorowany, jeśli każdy z jego krajów jest pomalowany określonym kolorem, a dowolne dwa kraje, które mają wspólną granicę, są pomalowane różnymi kolorami.

Przykład 4.Na płaszczyźnie jest n okręgów. Udowodnić, że dla dowolnego układu tych okręgów utworzoną przez nie mapę można poprawnie pokolorować dwoma kolorami.

Rozwiązanie.

Dla n=1 nasze stwierdzenie jest oczywiste.

Załóżmy, że nasze stwierdzenie jest prawdziwe dla dowolnego odwzorowania utworzonego przez n okręgów i niech na płaszczyźnie znajduje się n+1 okręgów. Usuwając jedno z tych okręgów, otrzymujemy mapę, którą z założenia można poprawnie pokolorować dwoma kolorami, np. czarnym i białym.

Indukcja to metoda uzyskania ogólnego stwierdzenia na podstawie konkretnych obserwacji. W przypadku, gdy stwierdzenie matematyczne dotyczy skończonej liczby obiektów, można je udowodnić testując dla każdego obiektu. Na przykład stwierdzenie: „Każda dwucyfrowa liczba parzysta jest sumą dwóch liczb pierwszych” wynika z szeregu równości, które są całkiem możliwe do ustalenia:

10=5+5 12=5+7 14=7+7 16=5+11 . . . 92=3+89 94=5+89 96=7+89 98=19+79.

Metodę dowodu, w której twierdzenie sprawdza się dla skończonej liczby przypadków wyczerpujących wszystkie możliwości, nazywa się indukcją zupełną. Metodę tę stosuje się stosunkowo rzadko, gdyż twierdzenia matematyczne z reguły nie dotyczą skończonych, ale nieskończonych zbiorów obiektów. Na przykład stwierdzenie o liczbach parzystych dwucyfrowych udowodnione powyżej przez indukcję całkowitą jest tylko szczególnym przypadkiem twierdzenia: „Każda liczba parzysta jest sumą dwóch liczb pierwszych”. Twierdzenie to nie zostało jeszcze udowodnione ani obalone.

Indukcja matematyczna to metoda udowodnienia pewnego twierdzenia dla dowolnej liczby naturalnej n w oparciu o zasadę indukcji matematycznej: „Jeśli twierdzenie jest prawdziwe dla n=1 i jego ważność dla n=k implikuje ważność tego twierdzenia dla n=k +1, to jest to prawdą dla wszystkich n ” Metoda dowodu metodą indukcji matematycznej jest następująca:

1) podstawa indukcji: dowodzą lub bezpośrednio sprawdzają zasadność twierdzenia dla n=1 (czasami n=0 lub n=n 0);

2) krok indukcyjny (przejście): zakładają ważność twierdzenia dla pewnej liczby naturalnej n=k i na podstawie tego założenia dowodzą ważności twierdzenia dla n=k+1.

Problemy z rozwiązaniami

1. Udowodnij, że dla dowolnej liczby naturalnej n liczba 3 2n+1 +2 n+2 jest podzielna przez 7.

Oznaczmy A(n)=3 2n+1 +2 n+2.

Podstawa indukcyjna. Jeśli n=1, to A(1)=3 3 +2 3 =35 i oczywiście jest podzielne przez 7.

Założenie indukcyjne. Niech A(k) będzie podzielne przez 7.

Przejście indukcyjne. Udowodnijmy, że A(k+1) jest podzielne przez 7, czyli zasadność twierdzenia problemu dla n=k.

A(k+1)=3 2(k+1)+1 +2 (k+1)+2 =3 2k+1 ·3 2 +2 k+2 ·2 1 =3 2k+1 ·9+2 k+2 ·2=

3 2k+1 9+2 k+2 (9–7)=(3 2k+1 +2 k+2) 9–7 2 k+2 =9 A(k)–7 2 k +2.

Ostatnia liczba jest podzielna przez 7, ponieważ jest różnicą dwóch liczb całkowitych podzielnych przez 7. Zatem 3 2n+1 +2 n+2 jest podzielne przez 7 dla dowolnej liczby naturalnej n.

2. Udowodnić, że dla dowolnej liczby naturalnej n liczba 2 3 n +1 jest podzielna przez 3 n+1 i niepodzielna przez 3 n+2.

Wprowadźmy zapis: a i =2 3 i +1.

Dla n=1 mamy i 1 =2 3 +1=9. Zatem 1 jest podzielna przez 3 2 i nie jest podzielna przez 3 3.

Niech dla n=k liczba a k jest podzielna przez 3 k+1 i niepodzielna przez 3 k+2, czyli a k =2 3 k +1=3 k+1 m, gdzie m nie jest podzielne przez 3. Wtedy

oraz k+1 =2 3 k+1 +1=(2 3 k) 3 +1=(2 3 k +1)(2 3 k ·2 –2 3 k +1)=3 k+1 ·m· ((2 3 k +1) 2 –3·2 3 k)=3 k+1 ·m·((3 k+1 ·m) 2 –3·2 3 k)=

3 k+2 ·m·(3 2k+1 ·m 2 –2 3 k).

Oczywiście a k+1 jest podzielne przez 3 k+2 i nie jest podzielne przez 3 k+3.

Zatem twierdzenie można udowodnić dla dowolnej liczby naturalnej n.

3. Wiadomo, że x+1/x jest liczbą całkowitą. Udowodnić, że x n +1/x n jest także liczbą całkowitą dla dowolnej liczby całkowitej n.

Wprowadźmy zapis: a i =х i +1/х i i od razu zauważmy, że a i =а –i, więc będziemy dalej mówić o indeksach naturalnych.

Uwaga: 1 jest zgodnie z konwencją liczbą całkowitą; i 2 jest liczbą całkowitą, ponieważ a 2 = (a 1) 2 –2; i 0 =2.

Załóżmy, że a k jest liczbą całkowitą dla dowolnej liczby naturalnej k nieprzekraczającej n. Wtedy a 1 ·a n jest liczbą całkowitą, ale a 1 ·a n =a n+1 +a n–1 i a n+1 =a 1 ·a n –a n–1 . Jednakże n–1, zgodnie z hipotezą indukcyjną, jest liczbą całkowitą. Oznacza to, że n+1 jest również liczbą całkowitą. Zatem x n +1/x n jest liczbą całkowitą dowolnej liczby całkowitej n, co należało udowodnić.

4. Udowodnić, że dla dowolnej liczby naturalnej n większej od 1 prawdziwa jest podwójna nierówność

5. Udowodnić, że dla naturalnych n > 1 i |x|

(1–x)n +(1+x)n

Dla n=2 nierówność jest prawdziwa. Naprawdę,

(1–x) 2 +(1+x) 2 = 2+2 x 2

Jeżeli nierówność jest prawdziwa dla n=k, to dla n=k+1 mamy

(1–x) k+1 +(1+x) k+1

Nierówność została udowodniona dla dowolnej liczby naturalnej n > 1.

6. Na płaszczyźnie jest n okręgów. Udowodnić, że dla dowolnego układu tych okręgów utworzoną przez nie mapę można poprawnie pokolorować dwoma kolorami.

Skorzystajmy z metody indukcji matematycznej.

Dla n=1 stwierdzenie jest oczywiste.

Załóżmy, że twierdzenie jest prawdziwe dla dowolnego odwzorowania utworzonego przez n okręgów i niech na płaszczyźnie znajduje się n+1 okręgów. Usuwając jedno z tych okręgów otrzymamy mapę, którą zgodnie z przyjętym założeniem można poprawnie pokolorować dwoma kolorami (patrz pierwszy obrazek poniżej).

Przywróćmy zatem odrzucony okrąg i po jednej jego stronie, np. wewnątrz, zmieńmy kolor każdego obszaru na przeciwny (patrz drugi obrazek). Łatwo zauważyć, że w tym przypadku otrzymamy mapę poprawnie pokolorowaną dwoma kolorami, ale tylko teraz dla okręgów n+1, co należało udowodnić.

7. Wielokąt wypukły nazwiemy „pięknym”, jeśli zostaną spełnione następujące warunki:

1) każdy jego wierzchołek jest pomalowany na jeden z trzech kolorów;

2) dowolne dwa sąsiednie wierzchołki są pomalowane różnymi kolorami;

3) co najmniej jeden wierzchołek wielokąta jest pomalowany w każdym z trzech kolorów.

Udowodnić, że każdy piękny n-gon można pociąć za pomocą rozłącznych przekątnych na „piękne” trójkąty.

Skorzystajmy z metody indukcji matematycznej.

Podstawa indukcyjna. Przy najmniejszym możliwym n=3 sformułowanie problemu jest oczywiste: wierzchołki „pięknego” trójkąta są pomalowane na trzy różne kolory i nie są potrzebne żadne cięcia.

Założenie indukcyjne. Załóżmy, że sformułowanie problemu jest prawdziwe dla dowolnego „pięknego” n-gonu.

Krok indukcyjny. Rozważmy dowolny „piękny” (n+1)-gon i udowodnijmy, korzystając z hipotezy indukcyjnej, że można go przeciąć niektórymi przekątnymi w „piękne” trójkąty. Oznaczmy przez A 1, A 2, A 3, ... An n, A n+1 kolejne wierzchołki kąta (n+1). Jeśli tylko jeden wierzchołek kąta (n+1) pokolorujemy na którykolwiek z trzech kolorów, to łącząc ten wierzchołek przekątnymi ze wszystkimi wierzchołkami z nim nie sąsiadującymi, otrzymamy niezbędny podział (n+1) )-gon w „piękne” trójkąty.

Jeżeli w każdym z trzech kolorów pokolorujemy co najmniej dwa wierzchołki kąta (n+1), to kolor wierzchołka A 1 oznaczamy numerem 1, a kolor wierzchołka A 2 numerem 2. Niech k będzie najmniejszą liczbą taką, że wierzchołek A k zostanie pokolorowany trzecim kolorem. Wiadomo, że k > 2. Odetnijmy trójkąt A k–2 A k–1 A k z (n+1)-kąta o przekątnej A k–2 A k. Zgodnie z wyborem liczby k wszystkie wierzchołki tego trójkąta są pomalowane na trzy różne kolory, czyli ten trójkąt jest „piękny”. Wypukły n-kąt A 1 A 2 ... A k–2 A k A k+1 ... A n+1 , który pozostanie, również na mocy założenia indukcyjnego będzie „piękny”, co oznacza jest on podzielony na „piękne” trójkąty, które i trzeba było udowodnić.

8. Udowodnij, że w n-kącie wypukłym nie można wybrać więcej niż n przekątnych, tak aby dowolne dwie miały wspólny punkt.

Dowód przeprowadźmy metodą indukcji matematycznej.

Udowodnijmy bardziej ogólne stwierdzenie: w n-kącie wypukłym nie można wybrać więcej niż n boków i przekątnych, tak aby dowolne dwa z nich miały wspólny punkt. Dla n = 3 stwierdzenie jest oczywiste. Załóżmy, że to stwierdzenie jest prawdziwe dla dowolnego n-gonu i wykorzystując to udowodnimy jego ważność dla dowolnego (n+1)-gonu.

Załóżmy, że to stwierdzenie nie jest prawdziwe dla (n+1)-gon. Jeśli z każdego wierzchołka kąta (n+1) wychodzą nie więcej niż dwa wybrane boki lub przekątne, to w sumie wybiera się nie więcej niż n+1 z nich. Zatem z jakiegoś wierzchołka A wychodzą co najmniej trzy boki lub przekątne AB, AC, AD. Niech AC leży pomiędzy AB i AD. Ponieważ żaden bok lub przekątna wychodząca z punktu C i inna niż CA nie może jednocześnie przecinać AB i AD, z punktu C wychodzi tylko jedna wybrana przekątna CA.

Odrzucając punkt C wraz z przekątną CA, otrzymujemy wypukły n-kąt, w którym wybranych jest więcej niż n boków i przekątnych, z których dowolne dwa mają wspólny punkt. Dochodzimy zatem do sprzeczności z założeniem, że twierdzenie jest prawdziwe dla dowolnego wypukłego n-kątu.

Zatem dla (n+1)-gon stwierdzenie jest prawdziwe. Zgodnie z zasadą indukcji matematycznej twierdzenie jest prawdziwe dla każdego wypukłego n-kątu.

9. Na płaszczyźnie istnieje n prostych, z których żadne dwie nie są równoległe i żadne trzy nie przechodzą przez ten sam punkt. Na ile części te linie dzielą płaszczyznę?

Korzystając z elementarnych rysunków, można łatwo sprawdzić, że jedna prosta dzieli płaszczyznę na 2 części, dwie proste na 4 części, trzy proste na 7 części i cztery proste na 11 części.

Oznaczmy przez N(n) liczbę części, na które n linii prostych dzieli płaszczyznę. Można to zauważyć

N(2)=N(1)+2=2+2,

N(3)=N(2)+3=2+2+3,

N(4)=N(3)+4=2+2+3+4.

To naturalne, że tak zakładamy

N(n)=N(n–1)+n=2+2+3+4+5+…+n,

lub, jak łatwo to ustalić, korzystając ze wzoru na sumę n pierwszych wyrazów ciągu arytmetycznego,

N(n)=1+n(n+1)/2.

Udowodnimy słuszność tego wzoru za pomocą metody indukcji matematycznej.

Dla n=1 wzór został już sprawdzony.

Przyjmując założenie indukcyjne, rozważamy k+1 prostych spełniających warunki zadania. Wybierzmy z nich k prostych w sposób dowolny. Zgodnie z hipotezą indukcyjną podzielą płaszczyznę na 1+ k(k+1)/2 części. Pozostała (k+1) prosta zostanie podzielona przez wybrane k prostych na k+1 części i w związku z tym będzie przechodzić wzdłuż (k+1)-tej części, na którą płaszczyzna została już podzielona, a każda z tych części zostanie podzielona na 2 części, czyli dodana zostanie kolejna część k+1. Więc,

N(k+1)=N(k)+k+1=1+ k(k+1)/2+k+1=1+(k+1)(k+2)/2,

co było do okazania

10. W wyrażeniu x 1: x 2: ... : x n umieszcza się nawiasy, aby wskazać kolejność działań, a wynik zapisuje się jako ułamek zwykły:

(w tym przypadku każda z liter x 1, x 2, ..., x n znajduje się albo w liczniku ułamka, albo w mianowniku). Ile różnych wyrażeń można uzyskać w ten sposób, stosując wszystkie możliwe sposoby umieszczania nawiasów?

Przede wszystkim jasne jest, że w wynikowym ułamku x 1 będzie w liczniku. Jest prawie tak oczywiste, że x 2 będzie w mianowniku, niezależnie od tego, jak ułożone są nawiasy (znak dzielenia przed x 2 odnosi się albo do samego x 2, albo do jakiegoś wyrażenia zawierającego x 2 w liczniku).

Można założyć, że wszystkie pozostałe litery x 3, x 4, ..., x n można umieścić w liczniku lub mianowniku w sposób całkowicie dowolny. Wynika z tego, że w sumie można otrzymać 2 n–2 ułamków: każda z n–2 liter x 3, x 4, ..., x n może wystąpić niezależnie od pozostałych w liczniku lub mianowniku.

Udowodnimy to twierdzenie przez indukcję.

Przy n=3 możesz otrzymać 2 ułamki:

więc stwierdzenie jest prawdziwe.

Załóżmy, że jest to prawdą dla n=k i udowodnijmy to dla n=k+1.

Niech wyrażenie x 1:x 2: ... :x k po pewnym umieszczeniu nawiasów zostanie zapisane w postaci pewnego ułamka Q. Jeśli w tym wyrażeniu zamiast x k podstawimy x k:x k+1, to x k będzie w tym samym miejscu co było w ułamku Q, a x k+1 nie będzie tam, gdzie było x k (jeżeli w mianowniku było x k, to w liczniku będzie x k+1 i odwrotnie).

Teraz udowodnimy, że możemy dodać x k+1 w tym samym miejscu, w którym znajduje się x k. W ułamku Q po umieszczeniu nawiasów koniecznie znajdzie się wyrażenie w postaci q:x k, gdzie q jest literą x k–1 lub jakimś wyrażeniem w nawiasie. Zastępując q:x k wyrażeniem (q:x k):x k+1 =q:(x k ·x k+1), otrzymujemy oczywiście ten sam ułamek Q, gdzie zamiast x k jest x k ·x k+1 .

Zatem liczba wszystkich możliwych ułamków w przypadku n=k+1 jest 2 razy większa niż w przypadku n=k i wynosi 2 k–2 ·2=2 (k+1)–2. W ten sposób stwierdzenie zostało udowodnione.

Odpowiedź: 2 n–2 frakcji.

Problemy bez rozwiązań

1. Udowodnić, że dla dowolnego naturalnego n:

a) liczba 5 n –3 n +2n jest podzielna przez 4;

b) liczba n 3 +11n jest podzielna przez 6;

c) liczba 7 n +3n–1 jest podzielna przez 9;

d) liczba 6 2n +19 n –2 n+1 jest podzielna przez 17;

e) liczba 7 n+1 +8 2n–1 jest podzielna przez 19;

e) liczba 2 2n–1 –9n 2 +21n–14 jest podzielna przez 27.

2. Udowodnij, że (n+1)·(n+2)· …·(n+n) = 2 n ·1·3·5·…·(2n–1).

3. Udowodnij nierówność |sin nx| n|grzech x| dla dowolnego naturalnego n.

4. Znajdź liczby naturalne a, b, c, które nie są podzielne przez 10 i takie, że dla dowolnego naturalnego n liczby a n + b n i c n mają te same dwie ostatnie cyfry.

5. Udowodnij, że jeśli n punktów nie leży na tej samej prostej, to wśród łączących je linii jest co najmniej n różnych.

Savelyeva Ekaterina

W artykule omówiono zastosowanie metody indukcji matematycznej do rozwiązywania problemów podzielności i sumowania szeregów. Rozważane są przykłady zastosowania metody indukcji matematycznej do dowodzenia nierówności i rozwiązywania problemów geometrycznych. Praca ilustrowana jest prezentacją.

Pobierać:

Zapowiedź:

Ministerstwo Nauki i Edukacji Federacji Rosyjskiej

Państwowa instytucja edukacyjna

gimnazjum nr 618

Przedmiot: algebra i podstawy analizy

Temat pracy projektowej

„Metoda indukcji matematycznej i jej zastosowanie do rozwiązywania problemów”

Praca skończona: Savelyeva E, klasa 11B

Kierownik : Makarova T.P., nauczycielka matematyki, Szkoła Średnia GOU nr 618

1. Wstęp.

2.Metoda indukcji matematycznej w rozwiązywaniu problemów podzielności.

3. Zastosowanie metody indukcji matematycznej do sumowania szeregów.

4. Przykłady zastosowania metody indukcji matematycznej do dowodu nierówności.

5. Zastosowanie metody indukcji matematycznej do rozwiązywania problemów geometrycznych.

6. Wykaz wykorzystanej literatury.

Wstęp

Podstawą wszelkich badań matematycznych są metody dedukcyjne i indukcyjne. Dedukcyjna metoda rozumowania to wnioskowanie od ogółu do szczegółu, tj. rozumowanie, którego punktem wyjścia jest wynik ogólny, a punktem końcowym jest wynik szczegółowy. Indukcję stosuje się przy przechodzeniu od wyników szczegółowych do wyników ogólnych, tj. jest przeciwieństwem metody dedukcyjnej. Metodę indukcji matematycznej można porównać do postępu. Zaczynamy od najniższego, a w wyniku logicznego myślenia dochodzimy do najwyższego. Człowiek od zawsze dążył do postępu, do umiejętności logicznego rozwijania swojego myślenia, co oznacza, że sama natura przeznaczyła go do myślenia indukcyjnego. Choć zakres zastosowania metody indukcji matematycznej wzrósł, w szkolnych programach nauczania poświęca się jej niewiele czasu, a umiejętność myślenia indukcyjnego jest niezwykle istotna. Zastosowanie tej zasady do rozwiązywania problemów i dowodzenia twierdzeń dorównuje uwzględnianiu w praktyce szkolnej innych zasad matematycznych: wyłączonego środka, włączenia-wyłączenia, Dirichleta itp. Streszczenie to zawiera problemy z różnych działów matematyki, w których głównym narzędziem jest metoda wykorzystania indukcji matematycznej. Mówiąc o znaczeniu tej metody, A.N. Kołmogorow zauważył, że „zrozumienie i umiejętność stosowania zasady indukcji matematycznej jest dobrym kryterium dojrzałości, absolutnie niezbędnej dla matematyka”. Metoda szeroko rozumianej indukcji polega na przejściu od szczegółowych obserwacji do uniwersalnego, ogólnego wzoru lub ogólnego sformułowania. W tej interpretacji metoda jest oczywiście główną metodą prowadzenia badań w każdej eksperymentalnej nauce przyrodniczej.

ludzka aktywność. Metodę (zasadę) indukcji matematycznej w najprostszej postaci stosuje się, gdy konieczne jest udowodnienie pewnego twierdzenia dla wszystkich liczb naturalnych.

Zadanie 1. W swoim artykule „Jak zostałem matematykiem” A.N. Kołmogorow pisze: „Wcześnie nauczyłem się radości z „odkrycia” matematycznego, zauważając pewien wzór w wieku pięciu lub sześciu lat

1 =1 2 ,

1 + 3 = 2 2 ,

1 + 3 + 5 = 3 2,

1 + 3 + 5 + 7 = 4 2 i tak dalej.

Szkoła wydawała czasopismo „Wiosenne Jaskółki”. Opublikowano w nim moje odkrycie…”

Nie wiemy, jakiego rodzaju dowody przedstawiono w tym czasopiśmie, ale wszystko zaczęło się od prywatnych obserwacji. Sama hipoteza, która prawdopodobnie powstała po odkryciu tych cząstkowych równości, jest taka, że formuła

1 + 3 + 5 + ... + (2n - 1) = n 2

prawdziwe dla dowolnej liczby n = 1, 2, 3, ...

Aby udowodnić tę hipotezę, wystarczy ustalić dwa fakty. Po pierwsze, za n = 1 (a nawet dla n = 2, 3, 4) żądane stwierdzenie jest prawdziwe. Po drugie, załóżmy, że stwierdzenie jest prawdziwe dla p = k, i upewnimy się, że wtedy będzie to również prawdą dla n = k + 1:

1 + 3 + 5+…+ (2k - 1) + (2k + 1) = (1 + 3 + 5 + ... + (2k - 1)) + (2k + 1) = k 2 + (2k + 1) = (k + ja) 2.

Oznacza to, że dowodzone twierdzenie jest prawdziwe dla wszystkich wartości n: dla n = 1 to prawda (sprawdzono), a z uwagi na drugi fakt – dla n = 2, skąd dla n = 3 (z tego samego, drugiego faktu) itd.

Zadanie 2. Rozważ wszystkie możliwe ułamki zwykłe z licznikiem 1 i dowolną (dodatnią liczbą całkowitą)

(nominalny) mianownik: Udowodnij to dla dowolnego p> 3 możemy przedstawić jednostkę jako sumę P różne frakcje tego typu.

Rozwiązanie, Najpierw sprawdźmy to stwierdzenie dla n = 3; mamy:

Zatem podstawowe stwierdzenie jest spełnione

Załóżmy teraz, że interesujące nas stwierdzenie jest prawdziwe dla pewnej liczby Do, i udowodnij, że jest to prawdą również dla następującej po niej liczby Do + 1. Innymi słowy, załóżmy, że istnieje reprezentacja

w którym k terminy i wszystkie mianowniki są różne. Udowodnijmy, że wtedy możemy otrzymać reprezentację jedności jako sumę Do + 1 frakcje wymaganego typu. Zakładamy, że ułamki są malejące, to znaczy mianowniki (w reprezentacji jednostki przez sumę Do terminy) zwiększaj się od lewej do prawej, tak aby T - największy z mianowników. Otrzymamy potrzebną reprezentację w formie sumy(Do + 1) ułamek, jeśli podzielimy jeden ułamek, np. ostatni, na dwa. Można to zrobić, ponieważ

I dlatego

Ponadto wszystkie frakcje pozostały różne, ponieważ T był największym mianownikiem, i t + 1 > t i

t(t + 1) > t.

Ustaliliśmy zatem:

z n = 3 to stwierdzenie jest prawdziwe;

jeśli interesujące nas stwierdzenie jest prawdziwe Do,
wtedy jest to również prawdą k + 1.

Na tej podstawie możemy stwierdzić, że omawiane twierdzenie jest prawdziwe dla wszystkich liczb naturalnych, począwszy od trójki. Co więcej, powyższy dowód implikuje również algorytm znajdowania wymaganego podziału jedności. (Co to za algorytm? Wyobraź sobie liczbę 1 jako sumę 4, 5, 7 samych wyrazów.)

Rozwiązując dwa poprzednie problemy, podjęto dwa kroki. Pierwszy krok to tzw podstawa indukcja, druga -złącze indukcyjnelub etap indukcji. Drugi krok jest najważniejszy i polega na przyjęciu założenia (twierdzenie jest prawdziwe kiedy n = k) i wniosek (twierdzenie jest prawdziwe, gdy n = k + 1). Wywoływany jest sam parametr n parametr indukcyjny.Ten schemat logiczny (technika), który pozwala stwierdzić, że dane stwierdzenie jest prawdziwe dla wszystkich liczb naturalnych (lub wszystkich, zaczynając od niektórych), ponieważ obowiązuje zarówno baza, jak i przejście, nazywa sięzasada indukcji matematycznej, na którym Opiera się na metodzie indukcji matematycznej.Samo określenie „indukcja” pochodzi od słowa łacińskiego wprowadzenie (przewodnictwo), co oznacza przejście od pojedynczej wiedzy o poszczególnych obiektach danej klasy do ogólnego wniosku o wszystkich przedmiotach danej klasy, co jest jedną z głównych metod poznania.

Zasada indukcji matematycznej, dokładnie w znanej formie dwóch kroków, pojawiła się po raz pierwszy w 1654 r. w „Traktacie o trójkącie arytmetycznym” Blaise’a Pascala, w którym udowodniono prosty sposób obliczania liczby kombinacji (współczynników dwumianowych) za pomocą indukcji. D. Polya cytuje B. Pascala z książki z drobnymi zmianami podanymi w nawiasach kwadratowych:

„Chociaż omawiana propozycja [wyraźny wzór na współczynniki dwumianu] zawiera niezliczoną ilość przypadków specjalnych, przedstawię na to bardzo krótki dowód, oparty na dwóch lematach.

Pierwszy lemat stwierdza, że założenie jest prawdziwe z jakiegoś powodu – to jest oczywiste. [Na P = obowiązuje 1 jawna formuła...]

Lemat drugi stwierdza, co następuje: jeśli nasze założenie jest prawdziwe dla dowolnej bazy [dla dowolnego r], to będzie ono prawdziwe z następującego powodu [dla n + 1].

Z tych dwóch lematów wynika koniecznie, że twierdzenie jest ważne dla wszystkich wartości P. Rzeczywiście, na mocy pierwszego lematu jest to prawdą P = 1; zatem na mocy drugiego lematu jest to prawdą dla P = 2; dlatego też, ponownie na mocy drugiego lematu, jest on ważny dla n = 3 i tak w nieskończoność.”

Zadanie 3. Układanka Wieże Hanoi składa się z trzech prętów. Na jednym z prętów znajduje się piramida (ryc. 1), składająca się z kilku pierścieni o różnych średnicach, zmniejszających się od dołu do góry

Ryc. 1

Piramidę tę należy przenieść na jeden z pozostałych prętów, za każdym razem przesuwając tylko jeden pierścień i nie umieszczając większego pierścienia na mniejszym. Czy jest to możliwe?

Rozwiązanie. Musimy więc odpowiedzieć na pytanie: czy możliwe jest przesunięcie piramidy składającej się z P pierścienie o różnych średnicach, od jednego pręta do drugiego, zgodnie z zasadami gry? Teraz mamy, jak to się mówi, sparametryzowane zadanie (wprowadzono liczbę naturalną P), i można to rozwiązać metodą indukcji matematycznej.

Podstawa indukcyjna. Kiedy n = 1 wszystko jest jasne, ponieważ piramidę jednego pierścienia można oczywiście przenieść na dowolny pręt.
Krok indukcyjny. Załóżmy, że możemy przesuwać dowolne piramidy o liczbę pierścieni p = k.
Udowodnijmy, że wtedy możemy przenieść pyra midka n = k + 1.

Piramida od do pierścienie leżące na największym(Do + 1)-ty pierścień, zgodnie z założeniem możemy go przenieść na dowolny inny pręt. Zróbmy to. bez ruchu(Do + 1)-ty pierścień nie przeszkodzi nam w wykonaniu algorytmu ruchu, ponieważ jest największy. Po przeprowadzce Do pierścienie, przesuńmy ten największy(Do + 1)ty pierścień na pozostałym pręcie. Następnie ponownie stosujemy algorytm ruchu znany nam z założenia indukcyjnego Do pierścienie i przesuń je na pręt z tym leżącym poniżej(Do + 1)-ty pierścień. Zatem, jeśli wiemy, jak przesuwać piramidy za pomocą Do pierścienie, wtedy wiemy, jak przesuwać piramidy i za pomocą Do + 1 pierścienie. Dlatego zgodnie z zasadą indukcji matematycznej zawsze można poruszyć piramidę składającą się z n pierścieni, gdzie n > 1.

Metoda indukcji matematycznej w rozwiązywaniu problemów podzielności.

Stosując metodę indukcji matematycznej można udowodnić różne twierdzenia dotyczące podzielności liczb naturalnych.

Problem 4 . Jeśli n jest liczbą naturalną, to jest to liczba parzysta.

Gdy n=1 prawdziwe jest nasze stwierdzenie: - liczba parzysta. Załóżmy, że jest to liczba parzysta. Ponieważ 2k jest liczbą parzystą, to jest parzysta. Zatem parzystość udowadnia się dla n=1, z parzystości wyprowadza się parzystość, co oznacza, że jest ona parzysta dla wszystkich naturalnych wartości n.

Zadanie 3. Udowodnij, że liczba Z 3 + 3 - 26n - 27 z dowolnym naturalnym n jest podzielne przez 26 2 bez reszty.

Rozwiązanie. Udowodnimy najpierw przez indukcję twierdzenie pomocnicze, że 3 3n+3 — 1 dzieli się przez 26 bez reszty, gdy n > 0.

Podstawa indukcyjna. Dla n = 0 mamy: 3 3 - 1 = 26 — podzielne przez 26.

Krok indukcyjny. Załóżmy, że 3 3n+3 - 1 dzieli się przez 26, gdy n = k, i Udowodnimy, że w tym przypadku stwierdzenie będzie prawdziwe dla n = k + 1. Od 3

wówczas z hipotezy indukcyjnej wnioskujemy, że liczba 3 3k + 6 - 1 jest podzielne przez 26.

Teraz udowodnimy twierdzenie sformułowane w stwierdzeniu problemu. I znowu przez indukcję.

Podstawa indukcyjna. Wiadomo, kiedy n = 1 stwierdzenie jest prawdziwe: od 3 3+3 - 26 - 27 = 676 = 26 2 .
Krok indukcyjny. Załóżmy, że kiedy p = k
wyrażenie 3 3k + 3 - 26k - 27 dzieli się przez 26 2 bez reszty i udowodnij, że stwierdzenie jest prawdziwe dla n = k + 1,
to znaczy ten numer

podzielna przez 26 2 bez śladu. W ostatniej sumie oba wyrazy są podzielne przez 26 2 . Po pierwsze, udowodniliśmy, że wyrażenie w nawiasach jest podzielne przez 26; druga opiera się na hipotezie indukcyjnej. Na mocy zasady indukcji matematycznej żądane stwierdzenie zostało całkowicie udowodnione.

Zastosowanie metody indukcji matematycznej do sumowania szeregów.

Zadanie 5. Udowodnić formułę

N jest liczbą naturalną.

Rozwiązanie.

Gdy n=1, obie strony równości zwracają się do jedynki, a zatem pierwszy warunek zasady indukcji matematycznej jest spełniony.

Załóżmy, że wzór jest poprawny dla n=k, tj.

Dodajmy obie strony tej równości i przekształćmy prawą stronę. Wtedy otrzymamy

Zadanie 6. Na tablicy zapisano dwie liczby: 1,1. Wpisując ich sumę pomiędzy liczby otrzymamy liczby 1, 2, 1. Powtarzając tę operację jeszcze raz otrzymamy liczby 1, 3, 2, 3, 1. Po trzech operacjach otrzymamy liczby 1, 4, 3 , 5, 2, 5, 3, 4, 1. Jaka będzie suma wszystkich liczb na planszy po 100 operacji?

Rozwiązanie. Zrób wszystko 100 byłoby zadaniem bardzo pracochłonnym i czasochłonnym. Oznacza to, że musimy spróbować znaleźć jakiś ogólny wzór na sumę S liczby po n operacje. Spójrzmy na tabelę:

Czy zauważyłeś tutaj jakiś wzór? Jeśli nie, możesz zrobić jeszcze jeden krok: po czterech operacjach pojawią się liczby

1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1,

którego suma S 4 jest równa 82.

Tak naprawdę nie możesz zapisywać liczb, ale od razu powiedzieć, jak zmieni się suma po dodaniu nowych liczb. Niech suma będzie równa 5. Co się stanie po dodaniu nowych liczb? Podzielmy każdą nową liczbę przez sumę dwóch starych. Na przykład od 1, 3, 2, 3, 1 przechodzimy do 1,

1 + 3, 3, 3 + 2, 2, 2 + 3, 3, 3 + 1, 1.

Oznacza to, że każda stara liczba (z wyjątkiem dwóch skrajnych jednostek) jest teraz uwzględniana w sumie trzy razy, więc nowa suma jest równa 3S - 2 (odejmij 2, aby uwzględnić brakujące jednostki). Dlatego S 5 = 3S 4 - 2 = 244 i ogólnie

Jaka jest ogólna formuła? Gdyby nie odjęcie dwóch jednostek, to za każdym razem suma zwiększałaby się trzykrotnie, jak w potęgach trzech (1, 3, 9, 27, 81, 243, ...). A nasze liczby, jak teraz widzimy, to jeszcze jeden. Można więc przypuszczać, że

Spróbujmy teraz udowodnić to przez indukcję.

Podstawa indukcyjna. Zobacz tabelę (dla n = 0, 1, 2, 3).

Krok indukcyjny. Udawajmy, że

Udowodnijmy to zatem S k + 1 = Z k + 1 + 1.

Naprawdę,

Zatem nasza formuła została sprawdzona. Pokazuje, że po stu operacjach suma wszystkich liczb na planszy będzie równa 3 100 + 1.

Spójrzmy na jeden świetny przykład zastosowania zasady indukcji matematycznej, w którym najpierw trzeba wprowadzić dwa parametry naturalne, a następnie przeprowadzić indukcję na ich sumie.

Zadanie 7. Udowodnij, że jeśli= 2, x 2 = 3 i dla każdego naturalnego p> 3 zależność zachodzi

x p = 3x p - 1 - 2x p - 2,

2 p - 1 + 1, p = 1, 2, 3, ...

Rozwiązanie. Należy pamiętać, że w tym zadaniu oryginalna sekwencja liczb(xp) wyznacza się przez indukcję, gdyż wyrazy naszego ciągu, z wyjątkiem dwóch pierwszych, są określone indukcyjnie, to znaczy poprzez poprzednie. Tak nazywane są podane ciągi nawracający, iw naszym przypadku ciąg ten jest wyznaczany (poprzez podanie dwóch pierwszych wyrazów) w sposób unikalny.

Podstawa indukcyjna. Polega na sprawdzeniu dwóch instrukcji: kiedy n = 1 i n = 2,V W obu przypadkach stwierdzenie jest prawdziwe ze względu na warunek.

Krok indukcyjny. Załóżmy, że dla n = k - 1 i n = k stwierdzenie jest spełnione, tzn

Udowodnijmy zatem zasadność twierdzenia dla n = k + 1. Mamy:

x 1 = 3(2 + 1) - 2(2 + 1) = 2+1, co należało udowodnić.

Zadanie 8. Udowodnić, że dowolną liczbę naturalną można przedstawić jako sumę kilku różnych wyrazów powtarzającego się ciągu liczb Fibonacciego:

dla k > 2.

Rozwiązanie. Niech n - Liczba naturalna. Indukcję przeprowadzimy dalej P.

Podstawa indukcyjna. Kiedy n = Stwierdzenie 1 jest prawdziwe, ponieważ jeden sam w sobie jest liczbą Fibonacciego.

Krok indukcyjny. Załóżmy, że wszystkie liczby naturalne są mniejsze od pewnej liczby P, można przedstawić jako sumę kilku różnych wyrazów ciągu Fibonacciego. Znajdźmy największą liczbę Fibonacciego Ft, nie lepszy P; zatem F t p i F t +1 > p.

Ponieważ

Według hipotezy indukcyjnej liczba n- F t można przedstawić jako sumę 5 kilku różnych wyrazów ciągu Fibonacciego, a z ostatniej nierówności wynika, że wszystkie wyrazy ciągu Fibonacciego biorące udział w sumie 8 są mniejsze Ft. Dlatego rozszerzenie liczby n = 8 + fa. t spełnia warunki problemu.

Przykłady zastosowania metody indukcji matematycznej do udowadniania nierówności.

Zadanie 9. (Nierówność Bernoulliego.)Udowodnij, że kiedy x > -1, x 0 i dla liczby całkowitej n > 2 nierówność jest prawdziwa

(1 + x) n > 1 + xn.

Rozwiązanie. Ponownie przeprowadzimy dowód przez indukcję.

1. Podstawa indukcji. Sprawdźmy zasadność nierówności dla n = 2. Rzeczywiście,

(1 + x) 2 = 1 + 2x + x 2 > 1 + 2x.

2. Krok indukcyjny. Załóżmy, że dla liczby p = k stwierdzenie jest prawdziwe, tzn

(1 + x) k > 1 + xk,

Gdzie k > 2. Udowodnijmy to dla n = k + 1. Mamy: (1 + x) k + 1 = (1 + x) k (1 + x)>(1 + kx)(1 + x) =

1 + (k + 1)x + kx 2 > 1 + (k + 1)x.

Zatem w oparciu o zasadę indukcji matematycznej możemy stwierdzić, że nierówność Bernoulliego jest prawdziwa dla dowolnego n > 2.

W kontekście problemów rozwiązywanych metodą indukcji matematycznej ogólne prawo, które należy udowodnić, nie zawsze jest jasno sformułowane. Czasami trzeba, obserwując poszczególne przypadki, najpierw odkryć (odgadnąć), do jakiego prawa ogólnego one prowadzą, a dopiero potem udowodnić postawioną hipotezę metodą indukcji matematycznej. Ponadto zmienną indukcyjną można zamaskować, a przed rozwiązaniem problemu należy określić, na jakim parametrze zostanie przeprowadzona indukcja. Jako przykłady rozważ następujące zadania.

Zadanie 10. Udowodnij to

pod jakimkolwiek naturalnym n > 1.

Rozwiązanie, Spróbujmy udowodnić tę nierówność metodą indukcji matematycznej.

Podstawę indukcji można łatwo zweryfikować:1+

Na podstawie hipotezy indukcyjnej

i pozostaje nam to udowodnić

Jeśli zastosujemy hipotezę indukcyjną, będziemy to argumentować

Chociaż ta równość jest rzeczywiście prawdziwa, nie daje nam rozwiązania problemu.

Spróbujmy udowodnić mocniejsze stwierdzenie, niż było to wymagane w pierwotnym zadaniu. Mianowicie, udowodnimy to

Wydawać by się mogło, że udowodnienie tego twierdzenia metodą indukcji jest sprawą beznadziejną.

Jednakże, gdy n = 1 mamy: stwierdzenie jest prawdziwe. Aby uzasadnić krok indukcyjny, załóżmy to

i wtedy to udowodnimy

Naprawdę,

Tym samym udowodniliśmy stwierdzenie silniejsze, z którego bezpośrednio wynika stwierdzenie zawarte w stwierdzeniu problemu.

Pouczającą rzeczą jest to, że chociaż musieliśmy udowodnić silniejsze twierdzenie niż jest to wymagane w zadaniu, w kroku indukcyjnym moglibyśmy zastosować mocniejsze założenie. To wyjaśnia, że proste zastosowanie zasady indukcji matematycznej nie zawsze prowadzi do celu.

Nazywano sytuację, która powstała podczas rozwiązywania problemuparadoks wynalazcy.Sam paradoks polega na tym, że bardziej złożone plany można z większym sukcesem realizować, jeśli opierają się na głębszym zrozumieniu istoty sprawy.

Zadanie 11. Udowodnij, że 2 m + n - 2 m dla każdego naturalnego typ.

Rozwiązanie. Tutaj mamy dwa parametry. Można zatem spróbować przeprowadzić tzwpodwójna indukcja(indukcja w indukcji).

Przeprowadzimy rozumowanie indukcyjne P.

1. Podstawa indukcyjna zgodnie z ust. Kiedy n = Muszę to sprawdzić 2 t ~ 1 > t. Aby udowodnić tę nierówność, używamy indukcji T.

A) Podstawa indukcyjna wg tzw Kiedy t = 1 wykonany
równość, co jest dopuszczalne.

B) Etap indukcyjny według tzwZałóżmy, że kiedy t = k stwierdzenie jest prawdziwe, tzn 2 tys. ~ 1 > tys. Potem do
powiedzmy, że stwierdzenie będzie prawdziwe także dla t = k + 1.
Mamy:

z naturalnym.

Zatem nierówność 2 wykonywane w dowolnym naturalnym T.

2. Stopień indukcyjny zgodnie z poz.Wybierzmy i ustalmy jakąś liczbę naturalną T. Załóżmy, że kiedy n = ja stwierdzenie jest prawdziwe (dla ustalonej t), czyli 2 t +1 ~ 2 > t1, i udowodnimy, że wtedy stwierdzenie będzie prawdziwe także dla n = l + 1.
Mamy:

dla każdego naturalnego typ.

Zatem bazując na zasadzie indukcji matematycznej (wg P) stwierdzenie problemu jest prawdziwe dla każdego P i dla każdego stałego T. Zatem ta nierówność dotyczy dowolnego naturalnego typ.

Zadanie 12. Niech m, n i k są liczbami naturalnymi i t > str. Która z tych dwóch liczb jest większa:

W każdym wyrażeniu Do znaki pierwiastkowe, t i p na przemian.

Rozwiązanie. Udowodnimy najpierw pewne twierdzenie pomocnicze.

Lemat. Dla każdego naturalnego t i p (t > p) i nieujemne (niekoniecznie całe) X nierówność jest prawdziwa

Dowód. Rozważ nierówność

Ta nierówność jest prawdziwa, ponieważ oba czynniki po lewej stronie są dodatnie. Rozwijając nawiasy i przekształcając, otrzymujemy:

Wyciągając pierwiastek kwadratowy z obu stron ostatniej nierówności, otrzymujemy stwierdzenie lematu. Zatem lemat został udowodniony.

Przejdźmy teraz do rozwiązania problemu. Oznaczmy pierwszą z tych liczb przez A, i drugi - przez b k. Udowodnijmy, że a pod jakimkolwiek naturalnym Do. Dowód przeprowadzimy metodą indukcji matematycznej oddzielnie dla parzystych i nieparzystych Do.

Podstawa indukcyjna. Kiedy k = 1 mamy nierówność

y[t > t/n , sprawiedliwe, ponieważ t > p. Kiedy k = 2 wymagane otrzymuje się ze sprawdzonego lematu przez podstawienie x = 0.

Krok indukcyjny. Załóżmy, że dla niektórych k nierówność a > b k sprawiedliwy. Udowodnijmy to

Z założenia indukcyjnego i pierwiastka kwadratowego monotoniczności mamy:

Natomiast ze sprawdzonego lematu wynika, że

Łącząc dwie ostatnie nierówności, otrzymujemy:

Zgodnie z zasadą indukcji matematycznej twierdzenie zostało udowodnione.

Problem 13. (Nierówność Cauchy'ego.)Udowodnić, że dla dowolnych liczb dodatnich..., str nierówność jest prawdziwa

Rozwiązanie. Dla n = 2 nierówność

założymy, że znana jest średnia arytmetyczna i średnia geometryczna (dla dwóch liczb). Pozwalać n= 2, k = 1, 2, 3, ... i najpierw wykonaj indukcję Do. Podstawą tej indukcji jest już założenie, że wymagana nierówność została już ustalona n = 2, udowodnijmy to P = 2 . Mamy (stosując nierówność dla dwóch liczb):

Dlatego zgodnie z hipotezą indukcyjną

Zatem przez indukcję po k udowodniliśmy nierówność dla wszystkich s. 9 będąc potęgą dwójki.

Aby udowodnić nierówność dla innych wartości P Użyjmy „indukcji w dół”, to znaczy udowodnimy, że jeśli nierówność zachodzi dla dowolnej nieujemnej P liczby, to dotyczy to również(P - 1 dzień. Aby to zweryfikować, zauważamy, że zgodnie z przyjętym założeniem P liczby, które spełnia nierówność

to znaczy a g + za 2 + ... + a n _ x > (n - 1)A. Podział obu części na P - 1, otrzymujemy wymaganą nierówność.

Zatem najpierw ustaliliśmy, że nierówność dotyczy nieskończonej liczby możliwych wartości P, a następnie pokazał, że jeśli nierówność jest spełniona P liczby, to dotyczy to również(P - 1) liczby. Z tego wnioskujemy teraz, że nierówność Cauty’ego zachodzi dla zbioru P dowolne liczby nieujemne dla dowolnego n = 2, 3, 4, ...

Zadanie 14. (D. Uspienski.) Dla dowolnego trójkąta ABC, którego kąty = CAB, = CBA są współmierne, występują nierówności

Rozwiązanie. Kąty i są współmierne, co (z definicji) oznacza, że kąty te mają wspólną miarę, dla której = p, = (p, q są względnie pierwszymi liczbami naturalnymi).

Skorzystajmy z metody indukcji matematycznej i przeprowadźmy ją przez sumę p = p + q naturalne liczby względnie pierwsze..

Podstawa indukcyjna. Dla p + q = 2 mamy: p = 1 i q = 1. Wtedy trójkąt ABC jest równoramienny, a niezbędne nierówności są oczywiste: wynikają z nierówności trójkąta

Krok indukcyjny. Załóżmy teraz, że niezbędne nierówności są ustalone dla p + q = 2, 3, ..., k - 1, gdzie k > 2. Udowodnijmy, że nierówności obowiązują również dla p + q = k.

Niech ABC - dany trójkąt, który ma> 2. Następnie boki AC i BC nie może być równe: niech AC > BC. Skonstruujmy teraz, jak na rysunku 2, trójkąt równoramienny ABC; mamy:

AC = DC i AD = AB + BD, zatem

2AC > AB + BD (1)

Rozważmy teraz trójkąt BDC, którego kąty są również proporcjonalne:

DСВ = (q - р), ВDC = p.

Ryż. 2

Dla tego trójkąta obowiązuje hipoteza indukcyjna, a zatem

(2)

Dodając (1) i (2) mamy:

2AC+BD>

i dlatego

Z tego samego trójkąta VBS z hipotezy indukcyjnej wnioskujemy, że

Biorąc pod uwagę poprzednią nierówność, dochodzimy do wniosku, że

W ten sposób uzyskuje się przejście indukcyjne, a sformułowanie problemu wynika z zasady indukcji matematycznej.

Komentarz. Sformułowanie problemu pozostaje ważne nawet w przypadku, gdy kąty a i p nie są współmierne. Na podstawie rozważań w przypadku ogólnym musimy już zastosować inną ważną zasadę matematyczną - zasadę ciągłości.

Zadanie 15. Kilka linii prostych dzieli płaszczyznę na części. Udowodnij, że możesz pokolorować te części na biało

i czarne kolory, tak aby sąsiednie części, które mają wspólny segment obramowania, miały różne kolory (jak na rysunku 3 z n = 4).

zdjęcie 3

Rozwiązanie. Skorzystajmy z indukcji po liczbie prostych. Więc pozwól P - ilość linii dzielących naszą płaszczyznę na części, n > 1.

Podstawa indukcyjna. Jeśli jest tylko jedna linia prosta(P = 1), to dzieli płaszczyznę na dwie półpłaszczyzny, z których jedną można pokolorować na biało, a drugą na czarno, a sformułowanie problemu jest prawdziwe.

Krok indukcyjny. Aby dowód przejścia indukcyjnego był bardziej przejrzysty, rozważ proces dodawania jednej nowej linii. Jeśli narysujemy drugą linię prostą(P= 2), wówczas otrzymujemy cztery części, które można pokolorować według potrzeb malując przeciwległe rogi tym samym kolorem. Zobaczmy, co się stanie, jeśli narysujemy trzecią linię prostą. Podzieli część „starych” części, pojawią się natomiast nowe odcinki granicy, których kolor będzie po obu stronach taki sam (ryc. 4).

Ryż. 4

Postępujmy w następujący sposób:Po jednej stroniez nowej prostej zmienimy kolory - biały zrobimy czarnym i odwrotnie; jednocześnie nie malujemy tych części, które leżą po drugiej stronie tej prostej (ryc. 5). Wtedy ta nowa kolorystyka spełni niezbędne wymagania: po jednej stronie linii była już naprzemienna (ale w różnych kolorach), a po drugiej stronie była tym, czego potrzebowano. Aby części posiadające wspólną granicę należącą do rysowanej linii zostały pomalowane na różne kolory, przemalowaliśmy części tylko po jednej stronie narysowanej linii prostej.

Ryc.5

Udowodnimy teraz przejście indukcyjne. Załóżmy, że dla niektórychp = kstwierdzenie problemu jest prawdziwe, to znaczy wszystkie części płaszczyzny, na które jest on przez nie podzielonyDoproste, możesz pomalować je na biało i czarno, aby sąsiadujące części miały różne kolory. Udowodnijmy, że w takim razie istnieje takie zabarwienie dlaP= Do+ 1 bezpośredni. Postępujmy podobnie jak w przypadku przejścia z dwóch linii do trzech. Narysujmy na samolocieDoprosty Następnie, korzystając z hipotezy indukcyjnej, powstałą „mapę” można pokolorować w pożądany sposób. Wykonajmy teraz(Do+ 1)prosta i po jednej jej stronie zmieniamy kolory na przeciwne. Więc teraz(Do+ 1)-ta prosta oddziela wszędzie obszary o różnych kolorach, podczas gdy „stare” części, jak już widzieliśmy, pozostają prawidłowo pokolorowane. Zgodnie z zasadą indukcji matematycznej problem został rozwiązany.

Zadanie16. Na skraju pustyni znajduje się duży zapas benzyny i samochód, który po pełnym zatankowaniu może przejechać 50 kilometrów. Istnieją nieograniczone ilości kanistrów, do których można wlać benzynę z baku samochodu i pozostawić ją do przechowania w dowolnym miejscu na pustyni. Udowodnić, że samochód może przejechać dowolną odległość całkowitą większą niż 50 kilometrów. Nie wolno wnosić kanistrów po benzynie, można wnosić puste w dowolnej ilości.

Rozwiązanie.Spróbujmy udowodnić przez indukcjęP,aby samochód mógł odjechaćPkilometrów od skraju pustyni. NaP= 50 jest znane. Pozostaje tylko przeprowadzić krok wprowadzający i wyjaśnić, jak się tam dostaćp = k+ 1 kilometr, jeśli to wiadomop = kMożna jeździć kilometrami.

Jednak tutaj napotykamy trudność: po tym, jak przeszliśmyDokilometrów benzyny może nie wystarczyć nawet na podróż powrotną (nie mówiąc już o jej przechowywaniu). I w tym przypadku rozwiązaniem jest wzmocnienie dowodzonego twierdzenia (paradoks wynalazcy). Udowodnimy, że można nie tylko jeździćPkilometrów, ale także w celu zapewnienia dowolnie dużej podaży benzyny w odległym punkciePkilometrów od skraju pustyni, docierając do tego miejsca po zakończeniu transportu.

Podstawa indukcyjna.Niech jednostką benzyny będzie ilość benzyny potrzebna do przebycia jednego kilometra. Wtedy na przejechanie 1 kilometra i z powrotem potrzebne są dwie jednostki benzyny, zatem możemy zostawić 48 jednostek benzyny w magazynie oddalonym o kilometr od krawędzi i wrócić po nową porcję. Dzięki temu w ciągu kilku wyjazdów do magazynu jesteśmy w stanie przygotować zapas o dowolnej wielkości, jakiej potrzebujemy. Jednocześnie, aby wytworzyć 48 jednostek rezerwy, zużywamy 50 jednostek benzyny.

Krok indukcyjny.Załóżmy, że na odległośćP= Doz krańca pustyni można zaopatrzyć się w dowolną ilość benzyny. Udowodnijmy, że wtedy możliwe jest stworzenie obiektu magazynowego na odległośćp = k+ 1 km z określonym wcześniej zapasem benzyny i kończy się w tym magazynie na koniec transportu. Ponieważ w punkcieP= Dobenzyny jest nieograniczona ilość, wówczas (wg bazy indukcyjnej) do pewnego punktu możemy dojść w kilka przejazdówp = k+ 1 zrób w punkcieP= Do4-1 zapas dowolnego wymaganego rozmiaru.

Prawdziwość stwierdzenia bardziej ogólnego niż w stwierdzeniu problemu wynika teraz z zasady indukcji matematycznej.

Wniosek

W szczególności studiując metodę indukcji matematycznej, pogłębiłem swoją wiedzę z tego obszaru matematyki, a także nauczyłem się rozwiązywać problemy, które wcześniej były poza moimi siłami.

W większości były to zadania logiczne i zabawne, tj. tylko te, które zwiększają zainteresowanie samą matematyką jako nauką. Rozwiązywanie takich problemów staje się zabawą i może przyciągać coraz więcej ciekawskich ludzi do matematycznych labiryntów. Moim zdaniem jest to podstawa każdej nauki.

Kontynuując naukę metody indukcji matematycznej, postaram się nauczyć, jak zastosować ją nie tylko w matematyce, ale także w rozwiązywaniu problemów w fizyce, chemii i samym życiu.

Literatura

1.INDUKCJA Vulenkina. Kombinatoryka. Podręcznik DLA nauczycieli. M., Oświecenie,

1976.-48 s.

2. Golovina L.I., Yaglom I.M. Indukcja w geometrii. - M.: Stan. opublikowany litr. - 1956 - S.I00. Podręcznik matematyki dla rozpoczynających naukę na uniwersytetach / wyd. Jakowlewa G.N. Nauka. -1981. - s. 47-51.

3.Golovina L.I., Yaglom I.M. Indukcja w geometrii. —
M.: Nauka, 1961. - (Popularne wykłady z matematyki.)

4. I.T.Demidov, A.N.Kolmogorov, S.I.Schvartsburg, O.S.Ivashev-Musatov, B.E.Weitz. Podręcznik / „Oświecenie” 1975.

5.R. Courant, G. Robbins „Co to jest matematyka?” Rozdział 1, § 2

6.Popa D. Matematyka i logiczne rozumowanie. - M,: Nauka, 1975.

7.Popa D. Odkrycie matematyczne. - M.: Nauka, 1976.

8. Rubanov I.S. Jak uczyć metody indukcji matematycznej / Szkoła matematyki. - Nl. - 1996. - s. 14-20.

9. Sominsky I.S., Golovina L.I., Yaglom IM. O metodzie indukcji matematycznej. - M.: Nauka, 1977. - (Popularne wykłady z matematyki.)

10.Solominsky I.S. Metoda indukcji matematycznej. - M.: Nauka.

63 s.

11.Solominsky I.S., Golovina L.I., Yaglom I.M. O indukcji matematycznej. - M.: Nauka. - 1967. - s. 7-59.

12.http://w.wikimedia.org/wiki

13.htt12:/ /www.refeshtcollestiop.ru/40 124.html

Lekcja wideo „Metoda indukcji matematycznej” pomoże Ci opanować metodę indukcji matematycznej. Film zawiera materiał, który pomoże Ci zrozumieć istotę metody, zapamiętać funkcje jej zastosowania i dowiedzieć się, jak zastosować tę metodę przy rozwiązywaniu problemów. Celem tego samouczka wideo jest ułatwienie opracowania materiału i rozwinięcie umiejętności rozwiązywania problemów matematycznych metodą indukcyjną.

Aby utrzymać uwagę uczniów na nauce materiału, zastosowano efekty animacji, ilustracje i kolorową prezentację informacji. Lekcja wideo uwalnia czas nauczyciela na zajęciach, aby poprawić jakość indywidualnej pracy i rozwiązać inne problemy edukacyjne.

Pojęcie metody indukcji matematycznej wprowadza się rozważając ciąg a n , w którym a 1 = 4 i a n+1 = a n +2n+3. Zgodnie z ogólną reprezentacją członu ciągu ustala się, że a 1 =4, a 2 =4+2.1+3=9, a 3 =9+2.2+3=16, czyli ciąg liczb 4, 9, 16,... Zakłada się, że dla tego ciągu prawdziwe jest n =(n+1) 2. Dla wskazanych wyrazów ciągu - pierwszego, drugiego, trzeciego - wzór jest poprawny. Konieczne jest udowodnienie ważności tego wzoru dla dowolnego dowolnie dużego n. Wskazuje się, że w takich przypadkach do udowodnienia twierdzenia stosuje się metodę indukcji matematycznej.

Ujawniono istotę metody. Zakłada się, że obowiązuje wzór na n=k, wartość a k =(k+1) 2 . Należy udowodnić, że równość będzie obowiązywać także dla k+1, czyli a k +1 =(k+2) 2 . Aby to zrobić, we wzorze a k +1 =a k +2k+3 zastępujemy k przez (k+1) 2. Po podstawieniu i redukcji podobnych otrzymujemy równość a k +1 =(k+2) 2 . Daje nam to prawo twierdzić, że ważność wzoru na n powoduje, że jest on prawdziwy dla n=k+1. Rozważany dowód w odniesieniu do ciągu a n , który jest reprezentowany przez liczby 4, 9, 16,... i ogólny wyraz a n = (n+1) 2, uprawnia do twierdzenia, że jeśli formuła zamieni się w prawdziwa równość dla n=1, to także dla n=1+ 1=2 i dla 3 itd., czyli dla dowolnej liczby naturalnej n.

Następnie w języku matematycznym przedstawiono istotę metody indukcyjnej. Zasada metody opiera się na ważności twierdzenia, że fakt zachodzi dla dowolnej liczby naturalnej n, gdy spełnione są dwa warunki: 1) stwierdzenie jest prawdziwe dla n=1 2) z ważności tego wzoru dla n= k wynika, że obowiązuje dla n=k+1. Z zasady tej wynika struktura dowodu, wykorzystując metodę indukcji matematycznej. Należy zauważyć, że metoda ta zakłada dla n=1 dowód ważności twierdzenia, a zakładając ważność dowodu dla n=k, okazuje się, że jest to prawdą również dla n=k+1.

Przeanalizowano przykład udowodnienia wzoru Archimedesa metodą indukcji matematycznej. Biorąc pod uwagę wzór 1 2 +2 2 +3 2 +…+n 2 =n(n+1)(2n+1)/6. Obliczenia przeprowadzane są na ekranie, aby wykazać ważność wzoru na n=1. Drugim punktem dowodu jest założenie, że dla n=k wzór jest ważny, czyli przyjmuje postać 1 2 +2 2 +3 2 +…+k 2 =k(k+1)(2k+1 )/6. Na tej podstawie dowodzi się, że wzór jest prawdziwy także dla n=k+1. Po podstawieniu n=k+1 otrzymujemy wartość wzoru 1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =(k+1)(k+2)(2k+3) /6. W ten sposób udowodniono wzór Archimedesa.

Inny przykład bada dowód wielokrotności 7 z sumy 15 n +6 dla dowolnej liczby naturalnej n. W dowodzie posługujemy się metodą indukcji matematycznej. Najpierw sprawdzamy ważność twierdzenia dla n=1. Rzeczywiście, 15 1 +6=21. Następnie zakładamy ważność dla n=k. Oznacza to, że 15 k +6 jest wielokrotnością 7. Podstawiając do wzoru n=k+1 udowadniamy, że wartość 15 k +1 +6 jest wielokrotnością 7. Po przekształceniu wyrażenia otrzymujemy: 15 k +1 +6=15 k +1 ·14+(15 k +6). Dlatego suma 15 n +6 jest wielokrotnością 7.

Lekcja wideo „Metoda indukcji matematycznej” jasno i szczegółowo ukazuje istotę i mechanizm stosowania metody indukcji matematycznej w dowodzie. Dlatego ten materiał wideo może służyć nie tylko jako pomoc wizualna na lekcji algebry, ale będzie przydatny podczas samodzielnego studiowania materiału przez ucznia i pomoże wyjaśnić nauczycielowi temat podczas nauki na odległość.