Metoda podsumowania lekcji indukcji matematycznej. Przykłady - indukcja matematyczna

METODA INDUKCJI MATEMATYCZNEJ

Słowo indukcja w języku rosyjskim oznacza wskazówki, a indukcyjne nazywa się wnioskami opartymi na obserwacjach, eksperymentach, tj. uzyskane przez wnioskowanie z konkretu do generała.

Na przykład codziennie 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 odwoływania się do jakichkolwiek założeń dotyczących przyczyny ruchu Słońca po niebie (co więcej, sam ten ruch okazuje się oczywisty, ponieważ kula ziemska faktycznie się porusza). A jednak to wyprowadzenie indukcyjne poprawnie opisuje obserwacje, które poczynimy jutro.

Rola wnioskowań indukcyjnych w naukach eksperymentalnych jest bardzo duża. Podają te przepisy, z których następnie wyciąga się dalsze wnioski przez odliczenie. I chociaż mechanika teoretyczna opiera się na trzech prawach dynamiki Newtona, same te prawa były wynikiem dogłębnego przemyślenia danych eksperymentalnych, w szczególności praw Keplera dotyczących ruchu planet, wyprowadzonych przez niego podczas przetwarzania długoterminowych obserwacji przez Duński astronom Tycho Brahe. Obserwacja i indukcja okazują się przydatne w przyszłości do dopracowania poczynionych założeń. Po eksperymentach Michelsona dotyczących pomiaru prędkości światła w poruszającym się ośrodku okazało się konieczne wyjaśnienie praw fizyki i stworzenie teorii względności.

W matematyce rola indukcji polega w dużej mierze na tym, że leży u podstaw wybranej aksjomatyki. Po długiej praktyce, która wykazała, że ​​droga prosta jest zawsze krótsza niż zakrzywiona lub łamana, naturalnym było sformułowanie aksjomatu: dla dowolnych trzech punktów A, B i C nierówność

Podstawowe pojęcie arytmetyki do naśladowania również wyłoniło się z obserwacji formowania się żołnierzy, statków i innych uporządkowanych zestawów.

Nie należy jednak sądzić, że na tym kończy się rola indukcji w matematyce. Oczywiście nie powinniśmy eksperymentalnie weryfikować twierdzeń, które są logicznie wydedukowane z aksjomatów: jeśli w wyprowadzeniu nie popełniono błędów logicznych, to są one prawdziwe, o ile przyjęte przez nas aksjomaty są prawdziwe. Ale z tego systemu aksjomatów można wywnioskować wiele stwierdzeń. A wybór tych stwierdzeń, które trzeba udowodnić, jest ponownie sugerowany przez indukcję. To ona pozwala nam oddzielić twierdzenia użyteczne od bezużytecznych, wskazuje, które twierdzenia mogą okazać się prawdziwe, a nawet pomaga wytyczyć drogę dowodu.

Istota metody indukcji matematycznej

W wielu działach arytmetyki, algebry, geometrii, analizy trzeba dowieść prawdziwości zdań A(n) zależnych od zmiennej naturalnej. Dowód prawdziwości zdania A(n) dla wszystkich wartości zmiennej często można przeprowadzić metodą indukcji matematycznej, która opiera się na następującej zasadzie.

Zdanie A(n) uważa się za prawdziwe dla wszystkich naturalnych wartości zmiennej, jeżeli spełnione są dwa 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 prawdziwe dla następnej wartości n=k+1.

Ta zasada nazywa się zasadą indukcji matematycznej. Jest on zwykle wybierany jako jeden z aksjomatów definiujących naturalny ciąg liczb, a zatem przyjmowany bez dowodu.

Przez metodę indukcji matematycznej rozumie się następującą metodę dowodową. Jeżeli wymagane jest udowodnienie prawdziwości zdania A(n) dla wszystkich naturalnych n, to po pierwsze należy sprawdzić prawdziwość zdania A(1), a po drugie założyć prawdziwość zdania A(k) spróbuj udowodnić, że zdanie A(k+1) jest prawdziwe. Jeżeli można to udowodnić, a dowód pozostaje ważny dla każdej naturalnej wartości k, to zgodnie z zasadą indukcji matematycznej zdanie A(n) uznaje się za prawdziwe dla wszystkich wartości n.

Metoda indukcji matematycznej jest szeroko stosowana w dowodzeniu 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 na

podzielność

Za pomocą metody indukcji matematycznej można dowieść różnych twierdzeń dotyczących podzielności liczb naturalnych.

Poniższe twierdzenie można stosunkowo łatwo udowodnić. Pokażmy, w jaki sposób uzyskuje się go metodą indukcji matematycznej.

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

Dla n=1 nasze stwierdzenie jest prawdziwe: - liczba parzysta. Załóżmy, że jest to liczba parzysta. Ponieważ 2k jest liczbą parzystą, więc nawet. Tak więc, parzystość jest udowodniona dla n=1, parzystość jest dedukowana z parzystości .Tak więc, nawet dla wszystkich wartości przyrodniczych n.

Przykład 2Udowodnij prawdziwość zdania

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

Rozwiązanie.

Zdanie A(1)=(liczba jest wielokrotnością 19) jest prawdziwe.

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

A(k)=(liczba jest wielokrotnością 19) jest prawdziwe. Następnie, ponieważ

Oczywiście A(k+1) również jest prawdziwe. Rzeczywiście, pierwszy wyraz jest podzielny przez 19 na podstawie założenia, że ​​A(k) jest prawdziwe; drugi wyraz jest również podzielny przez 19, ponieważ zawiera czynnik 19. Oba warunki zasady indukcji matematycznej są spełnione, zatem zdanie A(n) jest prawdziwe dla wszystkich wartości n.

Zastosowanie metody indukcji matematycznej do

sumowanie serii

Przykład 1Udowodnij formułę

, n jest liczbą naturalną.

Rozwiązanie.

Dla n=1 obie części równości zamieniają się w jeden, a zatem spełniony jest pierwszy warunek zasady indukcji matematycznej.

Załóżmy, że formuła jest prawdziwa dla n=k, tj.

.

Dodajmy do obu stron tej równości i przekształćmy prawą stronę. Wtedy dostajemy

Zatem z faktu, że wzór jest prawdziwy dla n=k wynika, że ​​jest on również prawdziwy dla n=k+1. To stwierdzenie jest prawdziwe dla każdej naturalnej wartości k. Tak więc spełniony jest również drugi warunek zasady indukcji matematycznej. Formuła została sprawdzona.

Przykład 2Wykazać, że suma pierwszych n liczb szeregu naturalnego wynosi .

Rozwiązanie.

Oznaczmy wymaganą kwotę , tj. .

Dla n=1 hipoteza jest prawdziwa.

Wynajmować . Pokażmy to .

Rzeczywiście,

Problem rozwiązany.

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

Rozwiązanie.

Wynajmować .

.

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.

Dla n=1 hipoteza jest oczywiście poprawna.

Wynajmować .

Udowodnijmy to.

Naprawdę,

Przykłady zastosowania metody indukcji matematycznej do

dowód nierówności

Przykład 1Udowodnij, że dla dowolnej liczby naturalnej n>1

.

Rozwiązanie.

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

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

Niech na trochę k. Udowodnijmy to 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 dlatego i .

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

Oświadczenie. Dla każdego naturalnego n nierówność jest prawdziwa.

Dowód.

. (1)

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

.

Rzeczywiście, co najmniej 2 dla dowolnego naturalnego k. Dodajmy nierówność (1) po lewej stronie, a po prawej 2. Otrzymujemy sprawiedliwą nierówność , lub . Twierdzenie zostało udowodnione.

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

Rozwiązanie.

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

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

. (1)

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

. (2)

Rzeczywiście, z założenia, zatem nierówność

, (3)

uzyskana z nierówności (1) przez pomnożenie każdej jej części przez . Zapiszmy nierówność (3) w następujący sposób: . Odrzucając dodatni wyraz po prawej stronie ostatniej nierówności, otrzymujemy obowiązującą nierówność (2).

Przykład 4 Udowodnij to

(1)

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

Rozwiązanie.

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

. (2)

Od , to nierówność

. (3)

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

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

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

. (4)

Udowodnijmy, że wtedy nierówność (1) musi być również słuszna dla n=k+1, tj.

(5)

Pomnóżmy obie części nierówności (4) przez a+b. Ponieważ z warunku otrzymujemy następującą uczciwą nierówność:

. (6)

Aby udowodnić nierówność (5), wystarczy wykazać, że:

, (7)

lub, co jest tym samym,

. (8)

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

. (9)

Jeśli , to i po lewej stronie nierówności (9) mamy iloczyn dwóch liczb dodatnich. Jeśli , to i po lewej stronie nierówności (9) mamy iloczyn dwóch liczb ujemnych. W obu przypadkach obowiązuje nierówność (9).

Dowodzi to, że słuszność nierówności (1) dla n=k implikuje jej słuszność dla n=k+1.

Metoda indukcji matematycznej w zastosowaniu do innych

zadania

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

Przykład 1Oblicz stronę poprawną - kwadrat wpisany w okrąg o promieniu R.

Rozwiązanie.

Dla n=2 poprawnie 2 n - kwadrat to kwadrat; jego strona. Dalej, zgodnie z formułą podwajania

odkryj, że bok ośmiokąta foremnego , strona sześciokąta foremnego , bok regularnego trzydziestu dwóch kątów . Możemy zatem założyć, że bok regularnego wpisanego 2 n - kwadrat dla dowolnego jest równy

. (1)

Załóżmy, że bok regularnego wpisanego -gonu wyraża się wzorem (1). W tym przypadku według wzoru podwojenia

,

stąd wynika, że ​​formuła (1) obowiązuje dla wszystkich n.

Przykład 2Na ile trójkątów można podzielić n-kąt (niekoniecznie wypukły) przez jego nie przecinające się przekątne?

Rozwiązanie.

Dla trójkąta liczba ta jest równa jeden (w trójkącie nie można rysować przekątnych); dla czworokąta liczba ta jest oczywiście równa dwóm.

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

Jakiś

A 1 A 2

Niech А 1 А k będzie jedną z przekątnych tej przegrody; dzieli n-gon А 1 А 2 …А n na k-gon A 1 A 2 …A k i (n-k+2)-gon А 1 А k A k+1 …A n . Zgodnie z przyjętym założeniem, łączna liczba trójkątów podziału będzie równa

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

w ten sposób nasze twierdzenie jest udowodnione dla wszystkich n.

Przykład 3Określ regułę obliczania liczby P(n) sposobów podziału n-kąta wypukłego na trójkąty nie przecinającymi się przekątnymi.

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 . W przypadku dowolnego podziału na trójkąty bok A 1 A 2 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 , А 4 , …, А n . Liczba sposobów podziału n-kąta, w którym ten wierzchołek pokrywa się z punktem A 3 , jest równa liczbie sposobów triangulacji (n-1)-kąta A 1 za 3 za 4 ... za n , tj. równa się P(n-1). Liczba sposobów podziału, w których ten wierzchołek pokrywa się z A 4 , jest równa liczbie sposobów podziału (n-2)-gon A 1 za 4 za 5 ... za n , tj. równa się P(n-2)=P(n-2)P(3); liczba sposobów 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 nie 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 relacji:

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

Korzystając z tej formuły otrzymujemy sukcesywnie:

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.

Również za pomocą metody indukcji matematycznej można rozwiązywać problemy z wykresami.

Niech na płaszczyźnie będzie dana sieć linii, łącząca ze sobą kilka punktów i nie posiadająca innych punktów. Taką sieć linii nazwiemy mapą, podane punkty są jej wierzchołkami, odcinki krzywych pomiędzy dwoma sąsiednimi wierzchołkami - granice mapy, części płaszczyzny, na które jest podzielona granicami - kraje Mapa.

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

Przykład 4Na płaszczyźnie jest n okręgów. Udowodnij, że dla dowolnego ułożenia tych okręgów, utworzona przez nie mapa może być poprawnie pokolorowana dwoma kolorami.

Rozwiązanie.

Dla n=1 nasze twierdzenie jest oczywiste.

Załóżmy, że nasze stwierdzenie jest prawdziwe dla dowolnego odwzorowania utworzonego przez n okręgów i niech na płaszczyźnie będzie dane n + 1 okręgów. Usuwając jedno z tych kółek, otrzymujemy mapę, która z założenia może być poprawnie pokolorowana dwoma kolorami, na przykład czarno-białym.

Savelyeva Jekaterina

W artykule rozważono zastosowanie metody indukcji matematycznej w rozwiązywaniu problemów podzielności, do sumowania szeregów. Rozważono przykłady zastosowania metody indukcji matematycznej do udowadniania nierówności i rozwiązywania problemów geometrycznych. Praca jest ilustrowana prezentacją.

Ściągnij:

Zapowiedź:

Ministerstwo Nauki i Edukacji Federacji Rosyjskiej

Państwowa instytucja edukacyjna

liceum nr 618

Kurs: Algebra i początki analizy

Temat prac projektowych

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

Praca skończona: Savelyeva E, klasa 11B

Kierownik : Makarova T.P., nauczycielka matematyki, gimnazjum 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

Metody dedukcyjne i indukcyjne są podstawą wszelkich badań matematycznych. Dedukcyjną metodą rozumowania jest rozumowanie od ogółu do szczegółu, tj. rozumowania, którego punktem wyjścia jest wynik ogólny, a punktem końcowym jest wynik szczegółowy. Indukcję stosuje się przy przejściu od wyników szczegółowych do wyników ogólnych, tj. jest przeciwieństwem metody dedukcyjnej. Metodę indukcji matematycznej można porównać z postępem. Zaczynamy od najniższego, w wyniku logicznego myślenia dochodzimy do najwyższego. Człowiek zawsze dążył do postępu, do zdolności logicznego rozwijania myśli, co oznacza, że ​​sama natura przeznaczyła go na myślenie indukcyjne. Choć pole zastosowania metody indukcji matematycznej się poszerzyło, w szkolnym programie nauczania poświęca się temu niewiele czasu, ale tak ważna jest umiejętność myślenia indukcyjnego. Zastosowanie tej zasady w rozwiązywaniu problemów i dowodzeniu twierdzeń jest na równi z uwzględnianiem w praktyce szkolnej innych zasad matematycznych: wykluczonego środka, inkluzji-wykluczenia, Dirichleta itp. Ten esej zawiera problemy z różnych działów matematyki, w których głównym narzędziem jest zastosowanie metody indukcji matematycznej. Mówiąc o znaczeniu tej metody, A.N. Kołmogorow zauważył, że „zrozumienie i umiejętność zastosowania zasady indukcji matematycznej jest dobrym kryterium dojrzałości, która jest absolutnie konieczna dla matematyka”. Metoda indukcji w najszerszym znaczeniu polega na przejściu od prywatnych obserwacji do uniwersalnego, ogólnego wzoru lub ogólnego sformułowania. W tej interpretacji metoda jest oczywiście główną techniką prowadzenia badań w każdej eksperymentalnej nauce przyrodniczej.

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

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

1 =1 2 ,

1 + 3 = 2 2 ,

1 + 3 + 5 \u003d W 2,

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

Szkoła wydawała pismo „Wiosenne Jaskółki”. W nim opublikowano moje odkrycie ... ”

Nie wiemy, jaki dowód został podany w tym dzienniku, 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

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

Aby udowodnić to przypuszczenie, wystarczy ustalić dwa fakty. Po pierwsze, dla n = 1 (a nawet dla n = 2, 3, 4) żądane stwierdzenie jest prawdziwe. Po drugie, załóżmy, że to stwierdzenie jest prawdziwe dla: n = k, i zweryfikuj, że wtedy jest to również prawdziwe dla n = k + 1:

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

Dlatego udowadniane twierdzenie jest prawdziwe dla wszystkich wartości n: dla n = 1 to prawda (to zostało zweryfikowane), a na mocy drugiego faktu, bo: n = 2, skąd dla n = 3 (ze względu na ten sam drugi fakt) itd.

Zadanie 2. Rozważ wszystkie możliwe zwykłe ułamki z licznikiem 1 i dowolnym (dodatnia liczba całkowita)

mianownik: Udowodnij to dla każdego n> 3 można przedstawić jako sumę P różne frakcje tego rodzaju.

Rozwiązanie, Najpierw sprawdźmy to twierdzenie pod kątem n = 3; mamy:

Zatem podstawowe twierdzenie jest spełnione

Załóżmy teraz, że interesujące nas stwierdzenie jest prawdziwe dla pewnej liczby do, i udowodnij, że dotyczy to również liczby następującej po niej 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żna uzyskać reprezentację jednostki w postaci sumy z do + 1 frakcje pożądanego typu. Przyjmiemy, że ułamki maleją, czyli mianowniki (w reprezentacji jednostki przez sumę do warunki) zwiększ od lewej do prawej, aby t jest największym z mianowników. Otrzymamy potrzebną reprezentację w postaci sumy(do + 1) ułamek, jeśli podzielimy jedną ułamek, na przykład ostatnią, na dwie. Można to zrobić, ponieważ

I dlatego

Ponadto wszystkie frakcje pozostają różne, ponieważ t był największym mianownikiem i t + 1 > t, oraz

m(t + 1) > m.

W ten sposób ustaliliśmy:

1. dla n = 3 to stwierdzenie jest prawdziwe;

1. czy interesujące nas stwierdzenie jest prawdziwe dla do,
   wtedy dotyczy to również do + 1.

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

W rozwiązaniu dwóch poprzednich problemów podjęto dwa kroki. Pierwszy krok to podstawa indukcja, drugaprzejście indukcyjnelub etap indukcji. Najważniejszy jest drugi krok, który wiąże się z założeniem (stwierdzenie jest prawdziwe dla n = k) i konkluzja (stwierdzenie jest prawdziwe dla n = k + 1). Sam parametr p nazywa się parametr indukcji.Ten schemat logiczny (urządzenie), który pozwala stwierdzić, że rozważane stwierdzenie jest prawdziwe dla wszystkich liczb naturalnych (lub dla wszystkich, zaczynając od niektórych), ponieważ zarówno podstawa, jak i przejście są ważne, nazywa sięzasada indukcji matematycznej, na którym i oparta jest metoda indukcji matematycznej.Sam termin „indukcja” pochodzi od łacińskiego słowa indukcja (przewodnictwo), co oznacza przejście od pojedynczej wiedzy o poszczególnych obiektach danej klasy do ogólnego wniosku o wszystkich obiektach danej klasy, co jest jedną z głównych metod poznania.

Zasada indukcji matematycznej, w zwykłej formie dwóch kroków, pojawiła się po raz pierwszy w 1654 r. w Traktacie Blaise'a Pascala o trójkącie arytmetycznym, w którym indukcja dowiodła prostego sposobu obliczenia liczby kombinacji (współczynników dwumianowych). D. Poya cytuje w książce B. Pascala z niewielkimi zmianami podanymi w nawiasach kwadratowych:

„Pomimo tego, że rozważane zdanie [jasna formuła na współczynniki dwumianowe] zawiera nieskończoną liczbę szczególnych przypadków, podam na to bardzo krótki dowód, oparty na dwóch lematach.

Pierwszy lemat mówi, że przypuszczenie jest prawdziwe dla bazy - jest to oczywiste. [Na P = 1 wyraźna formuła jest poprawna...]

Drugi lemat brzmi następująco: jeśli nasze założenie jest prawdziwe dla dowolnej bazy [dla dowolnego r], to będzie prawdziwe dla następującej bazy [dla n + 1].

Te dwa lematy z konieczności implikują słuszność twierdzenia dla wszystkich wartości P. Rzeczywiście, na mocy pierwszego lematu, obowiązuje dla: P = 1; dlatego na mocy drugiego lematu obowiązuje dla: P = 2; dlatego, ponownie na mocy drugiego lematu, obowiązuje dla: n = 3 i tak dalej w nieskończoność.

Zadanie 3. Wieże układanki Hanoi składają 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, opadających od dołu do góry

Rys. 1

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

Rozwiązanie. Musimy więc odpowiedzieć na pytanie: czy można przesunąć piramidę składającą się z P pierścienie o różnych średnicach, od jednej wędki do drugiej, zgodnie z zasadami gry? Teraz problem jest, jak mówią, sparametryzowany przez nas (liczba naturalna P), i można go rozwiązać za pomocą indukcji matematycznej.

1. podstawa indukcji. Dla n = 1, wszystko jest jasne, ponieważ piramidę jednego pierścienia można oczywiście przenieść na dowolny pręt.
2. krok indukcji. Załóżmy, że możemy przesunąć dowolne piramidy o liczbie pierścieni p = k.
   Udowodnijmy, że wtedy możemy również przesunąć środek piramidy z n = k + 1.

Piramida od do pierścionki leżące na największych(do + 1)-ty pierścień, możemy, zgodnie z założeniem, przesunąć się na dowolną inną oś. Zróbmy to. bez ruchu(do + 1) pierścień nie będzie nam przeszkadzał w przeprowadzeniu algorytmu przemieszczenia, ponieważ jest największy. Po przeprowadzce do pierścionki, przesuń ten największy(do + 1)-ty pierścień na pozostały pręt. A potem ponownie stosujemy algorytm poruszania znany nam przez założenie indukcyjne do pierścienie i przenieś je do pręta za pomocą(do + 1) pierścień. Tak więc, jeśli możemy przesuwać piramidy za pomocą do pierścienie, wtedy możemy przesuwać piramidy i do + 1 dzwonki. Dlatego zgodnie z zasadą indukcji matematycznej zawsze można przesunąć piramidę składającą się z n pierścieni, gdzie n > 1.

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

Za pomocą metody indukcji matematycznej można dowieść różnych twierdzeń dotyczących podzielności liczb naturalnych.

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

Dla n=1 nasze stwierdzenie jest prawdziwe: - liczba parzysta. Załóżmy, że jest to liczba parzysta. Ponieważ 2k jest liczbą parzystą, więc tak jest. Czyli parzystość jest udowodniona dla n=1, parzystość jest dedukowana z parzystości, stąd nawet 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. Wykażmy najpierw przez indukcję twierdzenie pomocnicze, że 3 3n+3 1 jest podzielne przez 26 bez reszty n > 0.

1. podstawa indukcji. Dla n = 0 mamy: Z 3 - 1 \u003d 26 - podzielone przez 26.

krok indukcji. Załóżmy, że 3 3n + 3 - 1 jest podzielne przez 26, gdy n = k, i Udowodnijmy, że w tym przypadku twierdzenie będzie prawdziwe dla n = k + 1. Ponieważ 3

następnie z założenia indukcyjnego wnioskujemy, że liczba 3 3k + 6 - 1 jest podzielne przez 26.

Udowodnijmy teraz twierdzenie sformułowane w warunkach problemu. I znowu przez indukcję.

1. podstawa indukcji. Oczywiste jest, że w n = 1 stwierdzenie jest prawdziwe: ponieważ 3 3+3 - 26 - 27 = 676 = 26 2 .
2. krok indukcji. Załóżmy, że w n = k
   wyrażenie 3 3k + 3 - 26k - 27 jest podzielne przez 26 2 bez reszty i udowodnij, że twierdzenie jest prawdziwe dla n = k + 1,
   czyli ten numer

podzielna przez 26 2 bez śladu. W ostatniej sumie oba wyrazy są dzielone bez reszty przez 26 2 . Pierwszym jest to, że udowodniliśmy, że wyrażenie w nawiasach jest podzielne przez 26; druga, przez hipotezę indukcyjną. Na mocy zasady indukcji matematycznej konieczne stwierdzenie jest całkowicie udowodnione.

Zastosowanie metody indukcji matematycznej do sumowania szeregów.

Zadanie 5. Udowodnij formułę

N jest liczbą naturalną.

Rozwiązanie.

Dla n=1 obie części równości zamieniają się w jeden, a zatem spełniony jest pierwszy warunek zasady indukcji matematycznej.

Załóżmy, że formuła jest prawdziwa dla n=k, tj.

Dodajmy do obu stron tej równości i przekształćmy prawą stronę. Wtedy dostajemy

Zatem z faktu, że wzór jest prawdziwy dla n=k wynika, że ​​jest on również prawdziwy dla n=k+1. To stwierdzenie jest prawdziwe dla każdej naturalnej wartości k. Tak więc spełniony jest również drugi warunek zasady indukcji matematycznej. Formuła została sprawdzona.

Zadanie 6. Na tablicy zapisane są dwie liczby: 1.1. Wpisując ich sumę między liczby, otrzymujemy liczby 1, 2, 1. Powtarzając tę ​​operację ponownie, otrzymujemy liczby 1, 3, 2, 3, 1. Po trzech operacjach liczby będą wynosić 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 operacje byłyby bardzo czasochłonne i czasochłonne. Musimy więc spróbować znaleźć 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 wynosi 82.

W rzeczywistości nie możesz wypisywać liczb, ale od razu powiedz, jak zmieni się suma po dodaniu nowych liczb. Niech suma będzie równa 5. Co to będzie po dodaniu nowych liczb? Podzielmy każdą nową liczbę na sumę dwóch starych. Na przykład z 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) wprowadza teraz sumę trzy razy, więc nowa suma to 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 odejmowanie dwóch jednostek, to za każdym razem suma wzrastałaby trzykrotnie, jak w potęgach trójki (1, 3, 9, 27, 81, 243, ...). A nasze liczby, jak teraz widzicie, to jeszcze jeden. Można więc założyć, że

Spróbujmy teraz to udowodnić indukcją.

podstawa indukcji. Zobacz tabelę (dla n = 0, 1, 2, 3).

krok indukcji. Udawajmy, że

Udowodnijmy więc, że S do + 1 \u003d Z do + 1 + 1.

Naprawdę,

Tak więc nasza formuła jest sprawdzona. Wynika z niego, że po stu operacjach suma wszystkich liczb na planszy będzie równa 3 100 + 1.

Rozważ jeden niezwykły przykład zastosowania zasady indukcji matematycznej, w którym najpierw musisz 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 n> 3

x n \u003d Zx n - 1 - 2x n - 2,

następnie

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

Rozwiązanie. Zauważ, że w tym zadaniu początkowy ciąg liczb(xn) jest zdeterminowana przez indukcję, ponieważ wyrazy naszego ciągu, z wyjątkiem pierwszych dwóch, są dane indukcyjnie, to znaczy przez poprzednie. Podane sekwencje nazywają się nawracający, aw naszym przypadku sekwencja ta jest określana (poprzez określenie jej pierwszych dwóch terminów) w unikalny sposób.

podstawa indukcji. Polega na sprawdzeniu dwóch asercji: n=1 i n=2.B W obu przypadkach twierdzenie jest prawdziwe z założenia.

krok indukcji. Załóżmy, że dla n = k - 1 i n = k wysuwa się twierdzenie, to znaczy

Udowodnijmy zatem twierdzenie o n = k + 1. Mamy:

x 1 = 3(2+1) - 2(2+1) = 2+1, co miało być udowodnione.

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

dla k > 2.

Rozwiązanie. Niech p - Liczba naturalna. Przeprowadzimy indukcję dnia P.

podstawa indukcji. Dla n = 1 stwierdzenie jest prawdziwe, ponieważ jednostka sama w sobie jest liczbą Fibonacciego.

krok indukcji. 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ź największą liczbę Fibonacciego F t , nieprzekraczającej P; więc F t n i F t +1 > n.

Ponieważ

Według hipotezy indukcyjnej liczba p- F t może być reprezentowana jako suma 5 różnych członków ciągu Fibonacciego, a z ostatniej nierówności wynika, że ​​wszystkie elementy ciągu Fibonacciego biorące udział w sumie 8 są mniejsze niż F t . Dlatego rozszerzenie liczby n = 8 + Ft spełnia stan problemu.

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

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

(1 + x) n > 1 + xn.

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

1. Podstawa indukcji. Zweryfikujmy słuszność nierówności dla n = 2. Rzeczywiście,

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

2. Krok indukcji. Załóżmy, że dla liczby n = k stwierdzenie jest prawdziwe, to znaczy

(1 + x) k > 1 + xk,

Gdzie k > 2. Udowadniamy 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.

Tak więc, w oparciu o zasadę indukcji matematycznej, można argumentować, że nierówność Bernoulliego obowiązuje dla każdego n > 2.

Nie zawsze w warunkach problemów rozwiązywanych metodą indukcji matematycznej ogólne prawo, które należy udowodnić, jest jasno sformułowane. Niekiedy trzeba, obserwując poszczególne przypadki, najpierw odkryć (zgadnąć), do jakiego ogólnego prawa prowadzą, a dopiero potem udowodnić postawioną hipotezę za pomocą indukcji matematycznej. Dodatkowo zmienną indukcyjną można maskować, a przed rozwiązaniem problemu konieczne jest określenie, na jakim parametrze zostanie przeprowadzona indukcja. Jako przykłady rozważ następujące zadania.

Problem 10. Udowodnij, że

dla każdego naturalnego n > 1.

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

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

Według hipotezy indukcyjnej

i pozostaje nam to udowodnić

Korzystając z hipotezy indukcyjnej, stwierdzimy, że

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

Spróbujmy dowieść silniejszego twierdzenia, niż jest to wymagane w pierwotnym zadaniu. Mianowicie udowodnimy, że

Może się wydawać, że udowodnienie tego twierdzenia przez indukcję jest beznadziejne.

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

a potem to udowodnimy

Naprawdę,

W ten sposób udowodniliśmy silniejsze twierdzenie, z którego bezpośrednio wynika twierdzenie zawarte w warunku problemu.

Pouczające jest to, że chociaż musieliśmy udowodnić silniejsze twierdzenie niż wymagane w zadaniu, moglibyśmy również użyć silniejszego założenia w kroku indukcyjnym. To wyjaśnia, że ​​proste zastosowanie zasady indukcji matematycznej nie zawsze prowadzi do celu.

Sytuacja, która pojawiła się w rozwiązaniu problemu, nazywa sięparadoks wynalazcy.Sam paradoks polega na tym, że bardziej złożone plany mogą być realizowane z większym powodzeniem, jeśli opierają się na głębszym zrozumieniu istoty sprawy.

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

Rozwiązanie. Tutaj mamy dwie opcje. Dlatego możesz spróbować przeprowadzić tzwpodwójna indukcja(indukcja w ramach indukcji).

Przeprowadzimy wnioskowanie indukcyjne na P.

1. Podstawa indukcji wg p. Dla n = Muszę to sprawdzić 2 t ~ 1 > t. Aby udowodnić tę nierówność, stosujemy indukcję na t.

a) Podstawa indukcji przez obj. Dla t = 1 w toku
równość, która jest do przyjęcia.

b) Krok indukcji wg t.Załóżmy, że w t = k stwierdzenie jest prawdziwe, to znaczy 2 tys. ~ 1 > tys. Następnie w górę
Powiedzmy, że twierdzenie jest prawdziwe, nawet jeśli: m = k + 1.
Mamy:

przy naturalnym k.

Tak więc nierówność 2 wykonywane dla każdego naturalnego t.

2. Krok indukcji zgodnie z pozycjąWybierz i napraw jakąś liczbę naturalną t. Załóżmy, że w n = I stwierdzenie jest prawdziwe (dla ustalonego t), tj. 2 t +1 ~ 2 > t1, i udowodnić, że wtedy twierdzenie będzie prawdziwe dla n = l + 1.
Mamy:

dla każdego naturalnego typ.

Dlatego w oparciu o zasadę indukcji matematycznej (zgodnie z P) stwierdzenie problemu jest prawdziwe dla każdego P i dla każdego ustalonego t. Tak więc ta nierówność dotyczy każdego naturalnego typ.

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

W każdym wyrazie do znaki pierwiastka kwadratowego, t i n na przemian.

Rozwiązanie. Udowodnijmy najpierw jakieś twierdzenie pomocnicze.

Lemat. Dla każdego naturalnego t i n (t > n) i nieujemna (niekoniecznie liczba całkowita) X nierówności

Dowód. Rozważ nierówność

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

Wyciągając pierwiastek kwadratowy z obu części ostatniej nierówności, otrzymujemy twierdzenie lematu. Więc lemat jest udowodniony.

Przejdźmy teraz do rozwiązania problemu. Oznaczmy pierwszą z tych liczb przez a, a drugi przez b do . Udowodnijmy, że dla każdego naturalnego do. Dowód zostanie przeprowadzony metodą indukcji matematycznej oddzielnie dla parzystych i nieparzystych do.

podstawa indukcji. Dla k = 1 mamy nierówność

r[t > r/n , co jest ważne ze względu na fakt, że m > rz. = 2, pożądany wynik uzyskuje się z udowodnionego lematu przez podstawienie x = 0.

krok indukcji. Załóżmy, dla niektórych do nierówności a >b do sprawiedliwy. Udowodnijmy, że

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

Z drugiej strony z udowodnionego lematu wynika, że:

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

Zgodnie z zasadą indukcji matematycznej twierdzenie to jest udowodnione.

Zadanie 13. (Nierówność Cauchy'ego.)Udowodnij, że dla dowolnych liczb dodatnich..., PI nierówności

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

średnia arytmetyczna i średnia geometryczna (dla dwóch liczb) będą uważane za znane. Wynajmować n= 2, k = 1, 2, 3, ... i najpierw przeprowadzić indukcję na do. Podstawa tej indukcji jest aktualna, zakładając teraz, że pożądana nierówność została już ustalona dla n = 2, udowodnimy to za P = 2 . Mamy (używając nierówności dla dwóch liczb):

Dlatego przez hipotezę indukcyjną

Zatem przez indukcję na k udowodniliśmy nierówność dla wszystkich s. 9 które są potęgami dwóch.

Aby udowodnić nierówność dla innych wartości P użyjemy „indukcji w dół”, czyli udowodnimy, że jeśli nierówność jest spełniona dla arbitralnie nieujemnych P liczb, obowiązuje również dla(P - 1) numer. Aby to zweryfikować, zauważamy, że zgodnie z przyjętym założeniem dla P liczby, nierówność

to znaczy a r + a 2 + ... + a n _ x > (n - 1) A. Dzieląc obie części na P - 1, uzyskujemy wymaganą nierówność.

Tak więc najpierw ustaliliśmy, że nierówność dotyczy nieskończonej liczby możliwych wartości P, a następnie pokazał, że jeśli nierówność utrzymuje się P liczb, obowiązuje również dla(P - 1) liczby. Z tego wnioskujemy teraz, że nierówność Coty'ego obowiązuje dla zbioru P dowolne liczby nieujemne dla dowolnego n = 2, 3, 4, ...

Problem 14. (D. Uspieński.) Dla dowolnego trójkąta ABC o kątach = CAB, = CBA są współmierne, istnieją nierówności

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

Użyjmy metody indukcji matematycznej i narysujmy ją nad sumą n = p + q naturalne liczby względnie pierwsze..

podstawa indukcji. Dla p + q = 2 mamy: p = 1 i q = 1. Wtedy trójkąt ABC jest równoramienny, a pożądane nierówności są oczywiste: wynikają z nierówności trójkąta

krok indukcji. Załóżmy teraz, że pożądane nierówności są ustalone dla p + q = 2, 3, ..., k - 1, gdzie k > 2. Udowodnijmy, że nierówności dotyczą również: p + q = k.

Niech ABC jest danym trójkątem z> 2. Następnie boki AC i BC nie może być równy: niech AC > BC. Teraz zbudujmy, jak na rysunku 2, trójkąt równoramienny ABC; mamy:

AC \u003d DC i AD \u003d AB + BD, zatem

2AC > AB + BD (1)

Rozważ teraz trójkąt VDC, których kąty są również porównywalne:

DCB = (q - p), BDC = p.

Ryż. 2

Ten trójkąt spełnia hipotezę indukcyjną, a zatem

(2)

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

2AC+BD>

i dlatego

Z tego samego trójkąta WBS na podstawie hipotezy indukcyjnej dochodzimy do wniosku, ż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. Stwierdzenie problemu pozostaje aktualne nawet wtedy, gdy kąty aip nie są współmierne. Na podstawie rozważań w ogólnym przypadku musimy już zastosować inną ważną zasadę matematyczną - zasadę ciągłości.

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

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

zdjęcie 3

Rozwiązanie. Stosujemy indukcję na ilość linii. Więc pozwól P - ilość linii dzielących nasz samolot na części, n > 1.

podstawa indukcji. Jeśli jest tylko jeden prosty(P = 1), to dzieli płaszczyznę na dwie półpłaszczyzny, z których jedna może być pokolorowana na biało, a druga na czarno, a stwierdzenie problemu jest prawdziwe.

krok indukcji. Aby dowód kroku indukcyjnego był bardziej przejrzysty, rozważ proces dodawania jednej nowej linii. Jeśli narysujemy drugą linię(P= 2), to otrzymujemy cztery części, które można pokolorować w żądany sposób, malując przeciwległe rogi na ten sam kolor. Zobaczmy, co się stanie, jeśli narysujemy trzecią prostą. Podzieli część „starych” części, a pojawią się nowe odcinki obramowania, po obu stronach tego samego koloru (rys. 4).

Ryż. cztery

Postępujmy następująco:jedna stronaz nowej prostej zmienimy kolory - zrobimy biały czarny i odwrotnie; jednocześnie te części, które leżą po drugiej stronie tej prostej, nie są przemalowywane (ryc. 5). Wtedy ta nowa kolorystyka spełni niezbędne wymagania: po jednej stronie prostej już była naprzemiennie (ale z różnymi kolorami), a po drugiej stronie była konieczna. Aby części, które mają wspólną granicę należącą do narysowanej linii, były pomalowane na różne kolory, przemalowaliśmy części tylko po jednej stronie tej narysowanej linii.

Rys.5

Udowodnijmy teraz krok indukcyjny. Załóżmy, że dla niektórychn = kstwierdzenie problemu jest poprawne, to znaczy wszystkie części płaszczyzny, na które jest podzielony przez tedoproste, można pomalować na biało i czarno, aby sąsiednie części miały różne kolory. Udowodnijmy, że w takim razie istnieje taka kolorystyka dlaP= do+ 1 prosty. Postępujmy podobnie jak w przypadku przejścia od dwóch prostych do trzech. Spędźmy w samolociedobezpośredni. Następnie, zgodnie z założeniem indukcyjnym, wynikową „mapę” można pokolorować w żądany sposób. Spędźmy teraz(do+ 1)-ta prosta i po jednej jej stronie zmieniamy kolory na przeciwne. Więc teraz(do+ 1)-ta linia prosta wszędzie oddziela sekcje o różnych kolorach, podczas gdy „stare” części, jak już widzieliśmy, pozostają prawidłowo zabarwione. Zgodnie z zasadą indukcji matematycznej problem został rozwiązany.

Zadanie16. Na skraju pustyni znajduje się duży zapas benzyny i samochód, który z pełną stacją benzynową może przejechać 50 kilometrów. W nieograniczonych ilościach dostępne są kanistry, do których można spuścić benzynę ze zbiornika paliwa samochodu i zostawić ją do przechowywania w dowolnym miejscu na pustyni. Udowodnij, że samochód może przejechać dowolną odległość całkowitą większą niż 50 kilometrów. Nie wolno przewozić puszek po benzynie, puste puszki można przewozić w dowolnej ilości.

Rozwiązanie.Spróbujmy to udowodnić przez indukcję naP,że samochód może jeździćPkilometrów od skraju pustyni. NaP= 50 jest znane. Pozostaje przeprowadzić etap indukcji i wyjaśnić, jak się tam dostaćn = k+ 1 km, jeśli jest znanyn = kkilometry można przejechać.

Tu jednak napotykamy na trudność: po przejściudokilometrów, benzyna może nawet nie wystarczyć na podróż powrotną (nie wspominając o magazynowaniu). A w tym przypadku wyjściem jest wzmocnienie udowadnionego twierdzenia (paradoks wynalazcy). Udowodnimy, że można nie tylko jeździćPkilometrów, ale także do wykonania dowolnie dużego zapasu benzyny w punkcie na odległośćPkilometrów od skraju pustyni, będąc w tym miejscu po zakończeniu transportu.

podstawa indukcji.Niech jednostką benzyny będzie ilość benzyny potrzebna do przejechania jednego kilometra podróży. Następnie 1 kilometrowa podróż i powrót wymaga dwóch jednostek benzyny, więc możemy zostawić 48 jednostek benzyny w magazynie kilometr od krawędzi i wrócić po więcej. W ten sposób na kilka wypraw do magazynu możemy wykonać zapas o dowolnej wielkości, której potrzebujemy. Jednocześnie, aby stworzyć 48 jednostek magazynowych, wydajemy 50 jednostek benzyny.

krok indukcji.Załóżmy, że na odległośćP= doz krawędzi pustyni możesz przechowywać dowolną ilość benzyny. Udowodnijmy, że wtedy można stworzyć repozytorium na odległośćn = k+ 1 km z dowolnym wcześniej ustalonym zapasem benzyny i znajdować się w tym miejscu na końcu transportu. Ponieważ w punkcieP= dojest nieograniczony zapas benzyny, wtedy (wg bazy indukcyjnej) możemy w kilku przejazdach do punktun = k+ 1 do zwrócenia uwagiP= do4- 1 zapas w dowolnym rozmiarze.

Prawda stwierdzenia bardziej ogólnego niż w stanie problemu teraz wynika z zasady indukcji matematycznej.

Wniosek

W szczególności, po przestudiowaniu metody indukcji matematycznej, poprawiłem swoją wiedzę w tym obszarze matematyki, a także nauczyłem się rozwiązywać problemy, które wcześniej były poza moją mocą.

W zasadzie 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ę zabawnym zajęciem i może przyciągać do matematycznych labiryntów coraz więcej dociekliwych ludzi. Moim zdaniem to podstawa każdej nauki.

Kontynuując naukę metody indukcji matematycznej, postaram się nauczyć jej zastosowania nie tylko w matematyce, ale także w rozwiązywaniu problemów z zakresu fizyki, chemii i samego życia.

Literatura

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

1976.-48 s.

2. Golovina LI, Jaglom I.M. Indukcja w geometrii. - M.: Gosud. wydawca oświetlony. - 1956 - S.I00. Podręcznik matematyki dla kandydatów na uniwersytety / wyd. Jakowlewa G.N. Nauka. -1981. - str.47-51.

3. Golovina LI, Jaglom IM. Indukcja w geometrii. —
M.: Nauka, 1961. - (Popularne wykłady z matematyki.)

4. IT Demidov, AN Kołmogorowa, S.I. Shvartsburg, OS Ivashev-Musatov, BE Veits. Podręcznik / „Oświecenie” 1975.

5.R. Courant, G Robbins "Czym jest matematyka?" Rozdział 1, § 2

6. Popa D. Matematyka i wnioskowanie wiarygodne. — M: Nauka, 1975.

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

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

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

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

63s.

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

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

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

Wykład 6. Metoda indukcji matematycznej.

Nową wiedzę w nauce i życiu zdobywa się na różne sposoby, ale wszystkie (jeśli nie wnikasz w szczegóły) dzielą się na dwa typy - przejście od ogółu do szczegółu i od szczegółu do ogółu. Pierwsza to dedukcja, druga to indukcja. Rozumowanie dedukcyjne jest zwykle nazywane w matematyce logiczne rozumowanie, a w naukach matematycznych dedukcja jest jedyną uprawnioną metodą badania. Zasady logicznego rozumowania zostały sformułowane dwa i pół tysiąca lat temu przez starożytnego greckiego naukowca Arystotelesa. Stworzył kompletną listę najprostszego poprawnego rozumowania, sylogizmy– „cegiełki” logiki, jednocześnie wskazując typowe rozumowanie, bardzo podobne do słusznych, ale błędne (często spotykamy się z takim „pseudologicznym” rozumowaniem w mediach).

Indukcja (indukcja - po łacinie przewodnictwo) ilustruje znana legenda o tym, jak Izaak Newton sformułował prawo powszechnego ciążenia po tym, jak jabłko spadło mu na głowę. Kolejny przykład z fizyki: w takim zjawisku, jak indukcja elektromagnetyczna, pole elektryczne wytwarza, „indukuje” pole magnetyczne. „Jabłko Newtona” jest typowym przykładem sytuacji, w której jeden lub więcej szczególnych przypadków, tj. obserwacje, „prowadzą” do ogólnego stwierdzenia, ogólny wniosek formułuje się na podstawie konkretnych przypadków. Metoda indukcyjna jest główną metodą uzyskiwania ogólnych wzorców zarówno w naukach przyrodniczych, jak i humanistycznych. Ma to jednak bardzo istotną wadę: na podstawie konkretnych przykładów można wyciągnąć błędny wniosek. Hipotezy wynikające z prywatnych obserwacji nie zawsze są poprawne. Rozważmy przykład Eulera.

Obliczymy wartość trójmianu dla kilku pierwszych wartości n:

Zauważ, że liczby uzyskane w wyniku obliczeń są pierwsze. I można to bezpośrednio zweryfikować dla każdego n Wartość wielomianu od 1 do 39
jest liczbą pierwszą. Jednak kiedy n=40 otrzymujemy liczbę 1681=41 2 , która nie jest liczbą pierwszą. Zatem hipoteza, która mogłaby tu powstać, czyli hipoteza, że ​​dla każdego n numer
jest proste, okazuje się fałszywe.

Leibniz udowodnił w XVII wieku, że na każdą dodatnią liczbę całkowitą n numer
podzielna przez 3
jest podzielna przez 5 i tak dalej. Na tej podstawie zasugerował, że dla każdego dziwactwa k i wszelkie naturalne n numer
podzielony przez k, ale szybko to zauważyłem
nie jest podzielna przez 9.

Rozważane przykłady pozwalają na wyciągnięcie ważnego wniosku: stwierdzenie może być prawdziwe w wielu szczególnych przypadkach, a jednocześnie niesprawiedliwe w ogólności. Kwestię słuszności twierdzenia w ogólnym przypadku można rozwiązać, stosując specjalną metodę rozumowania o nazwie przez indukcję matematyczną(indukcja pełna, indukcja doskonała).

6.1. Zasada indukcji matematycznej.

♦ Metoda indukcji matematycznej opiera się na zasada indukcji matematycznej , składający się z następujących elementów:

1) ważność tego oświadczenia jest weryfikowana dlan=1 (podstawa indukcji) ,

2) zakłada się, że to stwierdzenie jest prawdziwe dlan= k, gdziekjest dowolną liczbą naturalną 1(założenie indukcyjne) , a biorąc pod uwagę to założenie, jego ważność ustala się na:n= k+1.

Dowód. Załóżmy odwrotnie, to znaczy załóżmy, że twierdzenie nie jest prawdziwe dla każdego naturalnego n. Wtedy jest taki naturalny m, Co:

1) zatwierdzenie n=m niesprawiedliwe,

2) dla wszystkich n, mniejszy m, twierdzenie jest prawdziwe (innymi słowy, m jest pierwszą liczbą naturalną, dla której twierdzenie kończy się niepowodzeniem).

To oczywiste, że m>1, ponieważ dla n=1 stwierdzenie jest prawdziwe (warunek 1). W konsekwencji,
- Liczba naturalna. Okazuje się, że dla liczby naturalnej
stwierdzenie jest prawdziwe, a dla następnej liczby naturalnej m to nie fair. Jest to sprzeczne z warunkiem 2. ■

Zauważ, że w dowodach użyto aksjomatu, że każdy zbiór liczb naturalnych zawiera najmniejszą liczbę.

Dowód oparty na zasadzie indukcji matematycznej nazywa się przez całkowitą indukcję matematyczną .

 Przykład6.1. Udowodnij to dla każdego naturalnego n numer
jest podzielna przez 3.

Rozwiązanie.

1) Kiedy n=1 , więc a 1 jest podzielne przez 3, a stwierdzenie jest prawdziwe dla n=1.

2) Załóż, że stwierdzenie jest prawdziwe dla n=k,
, czyli ta liczba
jest podzielna przez 3 i znajdź to n=k+1 liczba jest podzielna przez 3.

Rzeczywiście,

Dlatego każdy wyraz jest podzielny przez 3, to ich suma jest również podzielna przez 3. ■ 

 Przykład6.2. Udowodnij, że suma pierwszych n naturalne liczby nieparzyste są równe kwadratowi ich liczby, czyli .

Rozwiązanie. Stosujemy metodę całkowitej indukcji matematycznej.

1) Sprawdzamy ważność tego oświadczenia pod kątem n=1: 1=1 2 jest poprawne.

2) Załóżmy, że suma pierwszego k (
) liczb nieparzystych jest równy kwadratowi liczby tych liczb, czyli . Na podstawie tej równości ustalamy, że suma pierwszych k+1 nieparzyste liczby to
, to znaczy .

Korzystamy z naszego założenia i otrzymujemy

. ■ 

Do udowodnienia niektórych nierówności stosuje się metodę całkowitej indukcji matematycznej. Udowodnijmy nierówność Bernoulliego.

 Przykład6.3. Udowodnij, że kiedy
i wszelkie naturalne n nierówności
(nierówność Bernoulliego).

Rozwiązanie. 1) Kiedy n=1 otrzymujemy
, który jest poprawny.

2) Zakładamy, że w n=k istnieje nierówność
(*). Korzystając z tego założenia udowadniamy, że
. Zauważ, że kiedy
ta nierówność utrzymuje się i dlatego wystarczy rozważyć przypadek
.

Pomnóż obie części nierówności (*) przez liczbę
i dostać:

To znaczy (1+
.■ 

Dowód metodą niepełna indukcja matematyczna pewne twierdzenie w zależności od n, gdzie
odbywa się w podobny sposób, ale na początku ustala się sprawiedliwość dla najmniejszej wartości n.

Niektóre problemy nie formułują wprost zdania, które można udowodnić za pomocą indukcji matematycznej. W takich przypadkach konieczne jest ustalenie prawidłowości i sformułowanie hipotezy o słuszności tej prawidłowości, a następnie przetestowanie zaproponowanej hipotezy metodą indukcji matematycznej.

 Przykład6.4. Znajdź kwotę
.

Rozwiązanie. Znajdźmy sumy S 1 , S 2 , S 3 . Mamy
,
,
. Przypuszczamy, że dla każdego naturalnego n formuła jest poprawna
. Aby sprawdzić tę hipotezę, posługujemy się metodą całkowitej indukcji matematycznej.

1) Kiedy n=1 hipoteza jest prawdziwa, ponieważ
.

2) Załóżmy, że hipoteza jest prawdziwa dla n=k,
, to znaczy
. Korzystając z tego wzoru ustalamy, że hipoteza jest prawdziwa i dla n=k+1, czyli

Rzeczywiście,

Zakładając więc, że hipoteza jest prawdziwa dla n=k,
, udowodniono, że tak jest w przypadku n=k+1 i na podstawie zasady indukcji matematycznej dochodzimy do wniosku, że wzór jest ważny dla każdego naturalnego n. ■ 

 Przykład6.5. W matematyce udowodniono, że suma dwóch funkcji jednostajnie ciągłych jest funkcją jednostajnie ciągłą. Na podstawie tego stwierdzenia musimy udowodnić, że suma dowolnej liczby
funkcji jednostajnie ciągłych jest funkcją jednostajnie ciągłą. Ale ponieważ nie wprowadziliśmy jeszcze pojęcia „funkcji jednostajnie ciągłej”, postawmy problem bardziej abstrakcyjnie: niech będzie wiadomo, że suma dwóch funkcji, które mają pewną własność S, sam ma właściwość S. Wykażmy, że suma dowolnej liczby funkcji ma własność S.

Rozwiązanie. Podstawą indukcji jest tutaj samo sformułowanie problemu. Dokonując założenia indukcyjnego, rozważ
Funkcje f 1 , f 2 , …, f n , f n+1, które mają właściwość S. Następnie . Po prawej stronie pierwszy termin ma własność S zgodnie z hipotezą indukcyjną drugi wyraz ma właściwość S według stanu. Dlatego ich suma ma własność S– przez dwa semestry podstawa indukcji „dzieła”.

To potwierdza twierdzenie i będzie je dalej wykorzystywać. ■ 

 Przykład6.6. Znajdź wszystkie naturalne n, dla których nierówności

.

Rozwiązanie. Rozważać n=1, 2, 3, 4, 5, 6. Mamy: 2 1 >1 2 , 2 2 =2 2 , 2 3<3 2 , 2 4 =4 2 , 2 5 >5 2 , 2 6 > 6 2 . W ten sposób możemy postawić hipotezę: nierówność
ma miejsce dla każdego
. Aby udowodnić prawdziwość tej hipotezy, posługujemy się zasadą niepełnej indukcji matematycznej.

1) Jak stwierdzono powyżej, ta hipoteza jest prawdziwa dla n=5.

2) Załóżmy, że to prawda dla n=k,
czyli nierówności
. Stosując to założenie dowodzimy, że nierówności
.

T. do.
i w
istnieje nierówność

w
,

wtedy to rozumiemy
. Tak więc słuszność hipotezy… n=k+1 wynika z założenia, że ​​jest prawdziwe dla n=k,
.

Od s. 1 i 2, w oparciu o zasadę niepełnej indukcji matematycznej, wynika, że ​​nierówność
prawdziwe dla każdego naturalnego
. ■ 

 Przykład6.7. Udowodnij, że dla dowolnej liczby naturalnej n formuła różniczkowania jest poprawna
.

Rozwiązanie. Na n=1 ta formuła ma postać
, czyli 1=1, to znaczy, że to prawda. Dokonując założenia indukcyjnego mamy:

co było do okazania ■ 

 Przykład6.8. Udowodnij, że zestaw składający się z n elementy, ma podzbiory.

Rozwiązanie. Zestaw z jednym elementem a, ma dwa podzbiory. Jest to prawdą, ponieważ wszystkie jego podzbiory są zbiorem pustym i samym zbiorem oraz 2 1 =2.

Zakładamy, że dowolny zestaw n elementy mają podzbiory. Jeśli zbiór A składa się z n+1 element, następnie naprawiamy w nim jeden element - oznaczamy go d i podziel wszystkie podzbiory na dwie klasy - nie zawierające d i zawierające d. Wszystkie podzbiory z pierwszej klasy są podzbiorami zbioru B uzyskanymi z A przez usunięcie elementu d.

Zestaw B składa się z n pierwiastków, a zatem, zgodnie z hipotezą indukcyjną, ma podzbiory, więc w pierwszej klasie podzbiory.

Ale w drugiej klasie jest taka sama liczba podzbiorów: każdy z nich jest uzyskiwany z dokładnie jednego podzbioru pierwszej klasy przez dodanie elementu d. Dlatego w sumie zbiór A
podzbiory.

W ten sposób twierdzenie jest udowodnione. Zauważ, że dotyczy to również zestawu składającego się z 0 elementów - zestawu pustego: ma on jeden podzbiór - siebie i 2 0 =1. ■ 

Korzystając z metody indukcji matematycznej udowodnij, że dla każdego naturalnego n prawdziwe są następujące równości:
a) ;
b) .

Rozwiązanie.

a) Kiedy n= 1 równość jest ważna. Zakładając ważność równości dla n, pokażmy, że obowiązuje również dla n+ 1. Rzeczywiście,

co było do okazania

b) Kiedy n= 1 ważność równości jest oczywista. Z założenia jej słuszności w n powinien

Biorąc pod uwagę równość 1 + 2 + ... + n = n(n+ 1)/2, otrzymujemy

1 3 + 2 3 + ... + n 3 + (n + 1) 3 = (1 + 2 + ... + n + (n + 1)) 2 ,

tj. stwierdzenie jest również prawdziwe dla n + 1.

Przykład 1 Udowodnij następujące równości

Rozwiązanie. a) Kiedy n= 1 równość przyjmie postać 1=1, zatem P(1) prawda. Załóżmy, że ta równość jest prawdziwa, czyli mamy

Tak więc, zgodnie z metodą indukcji matematycznej, pierwotna równość obowiązuje dla każdego naturalnego n.

Uwaga 2. Ten przykład można rozwiązać w inny sposób. Rzeczywiście, suma 1 + 2 + 3 + ... + n to suma pierwszego n członkowie progresji arytmetycznej z pierwszym członkiem a 1 = 1 i różnica d= 1. Ze względu na dobrze znaną formułę , dostajemy

b) Kiedy n= 1 równość przyjmie postać: 2 1 - 1 = 1 2 lub 1=1, czyli P(1) prawda. Załóżmy, że równość

1 + 3 + 5 + ... + (2n - 1) = n 2 i udowodnij, żeP(n + 1): 1 + 3 + 5 + ... + (2n - 1) + (2(n + 1) - 1) = (n+ 1) 2 lub 1 + 3 + 5 + ... + (2 n - 1) + (2n + 1) = (n + 1) 2 .

Stosując hipotezę indukcyjną otrzymujemy

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

W ten sposób, P(n+ 1) jest prawdziwe, a zatem udowodniono wymaganą równość.

Uwaga 3. Ten przykład można rozwiązać (podobnie jak poprzedni) bez użycia metody indukcji matematycznej.

c) Kiedy n= 1 równość jest prawdziwa: 1=1. Załóż, że równość jest prawdziwa

d) Kiedy n= 1 równość jest ważna: 1=1. Załóżmy, że istnieje

Naprawdę,

e) Zatwierdzenie P(1) prawda: 2=2. Załóżmy, że równość

Dlatego pierwotna równość obowiązuje dla każdego naturalnego n.

f) P(1) prawda: 1/3 = 1/3. Niech będzie równość P(n):

Rzeczywiście, biorąc pod uwagę to P(n) ma miejsce, otrzymujemy

W ten sposób udowodniono równość.

g) Kiedy n= 1 mamy a + b = b + a i stąd równość jest prawdziwa.

Niech dwumian Newtona będzie ważny dla n = k, to znaczy,

Przykład 2 Udowodnij nierówności

Rozwiązanie. a) Kiedy n= 1 otrzymujemy prawdziwą nierówność

1 + a ≥ 1 + a . Załóżmy, że istnieje nierówność

Rzeczywiście, ponieważ a > -1 implikuje a + 1 > 0, to mnożąc obie strony nierówności (1) przez (a + 1), otrzymujemy

(1 + a ) n(1 + a ) ≥ (1 + n a )(1 + a ) lub (1 + a ) n + 1 ≥ 1 + (n+ 1)a + n 2 Ponieważ n 2 ≥ 0, zatem(1 + a ) n + 1 ≥ 1 + (n+ 1)a + n a 2 ≥ 1 + ( n+ 1)a.

Tak więc, jeśli P(n) jest prawdziwe, to P(n+ 1) jest prawdziwe, zatem zgodnie z zasadą indukcji matematycznej nierówność Bernoulliego jest prawdziwa.

b) Kiedy n= 1 otrzymujemy x 1 = 1, a zatem x 1 ≥ 1 tj. P(1) jest uczciwym oświadczeniem. Udawajmy, że P(n) jest prawdziwe, to znaczy, jeśli adica, x 1 ,x 2 ,...,x n - n liczby dodatnie, których iloczyn jest równy jeden, x 1 x 2 ·...· x n= 1 i x 1 + x 2 + ... + x n ≥ n.

Pokażmy, że z tego twierdzenia wynika, że ​​prawdziwe jest: if x 1 ,x 2 ,...,x n ,x n+1 - (n+ 1) liczby dodatnie takie, że x 1 x 2 ·...· x n · x n+1 = 1, to x 1 + x 2 + ... + x n + x n + 1 ≥n + 1.

Rozważ następujące dwa przypadki:

1) x 1 = x 2 = ... = x n = x n+1 = 1. Wtedy suma tych liczb wynosi ( n+ 1), a wymagana nierówność jest spełniona;

2) co najmniej jedna liczba jest różna od jedności, niech na przykład będzie większa od jedynki. Wtedy, ponieważ x 1 x 2 · ... · x n · x n+ 1 = 1, istnieje co najmniej jedna inna liczba, która różni się od jedności (dokładniej mniej niż jeden). Wynajmować x n+ 1 > 1 i x n < 1. Рассмотрим n liczby dodatnie

Ponieważ

(1 - x n)(x n+1 - 1) > 0, to n + x n + x n+1 - x n x n+1 = n + 1 + x n+1 (1 - x n) - 1 + x n =
= n + 1 + x n+1 (1 - x n) - (1 - x n) = n + 1 + (1 - x n)(x n+1 - 1) ≥ n+ 1. Dlatego x 1 + x 2 + ... + x n + x n+1 ≥ n+1, czyli jeśli P(n) jest prawdziwe, toP(n+ 1) jest sprawiedliwy. Nierówność została udowodniona.

Uwaga 4. Znak równości występuje wtedy i tylko wtedy, gdy x 1 = x 2 = ... = x n = 1.

c) Niech x 1 ,x 2 ,...,x n są dowolnymi liczbami dodatnimi. Rozważ następujące n liczby dodatnie:

Uwaga 5. Równość obowiązuje wtedy i tylko wtedy, gdy x 1 = x 2 = ... = x n .

d) P(1) - sprawiedliwe stwierdzenie: sin 2 a + cos 2 a = 1. Załóżmy, że P(n) to prawdziwe stwierdzenie:

Grzech 2 n a + cos2 n a ≤ 1 i pokazać, że istniejeP(n+ 1). Naprawdę, grzech2( n+ 1) a + cos 2( n+ 1) \u003d grzech 2 n grzech 2 a + cos 2 n cos 2 a< sin 2n a + cos2 n a ≤ 1 (jeśli sin 2 a ≤ 1, to cos 2 a < 1, и обратно: если cos 2 a ≤ 1, to grzech 2 a < 1). Таким образом, для любого n O N grzech 2 n a + cos2 n ≤ 1, a znak równości jest osiągany tylko wtedy, gdyn = 1.

e) Kiedy n= 1 stwierdzenie jest prawdziwe: 1< 3 / 2 .

Załóżmy, że i udowodnij, że

f) Uwzględniając uwagę 1, sprawdzamy P(10): 2 10 > 10 3 , 1024 > 1000, zatem dla n= 10 stwierdzenie jest prawdziwe. Załóżmy 2 n > n 3 (n> 10) i udowodnij P(n+ 1), czyli 2 n+1 > (n + 1) 3 .

Ponieważ w n> 10 mamy lub , wynika z tego

2n 3 > n 3 + 3n 2 + 3n+ 1 lub n 3 > 3n 2 + 3n + 1. Uwzględnienie nierówności (2 n > n 3) otrzymujemy 2 n+1 = 2 n 2 = 2 n + 2 n > n 3 + n 3 > n 3 + 3n 2 + 3n + 1 = (n + 1) 3 .

Tak więc, zgodnie z metodą indukcji matematycznej, dla każdego naturalnego n O N, n≥ 10 mamy 2 n > n 3 .

Przykład 3 Udowodnij to dla każdego n O N

Rozwiązanie. a) P(1) jest prawdziwym stwierdzeniem (0 jest podzielne przez 6). Wynajmować P(n) jest sprawiedliwy, to znaczy n(2n 2 - 3n + 1) = n(n - 1)(2n- 1) jest podzielna przez 6. Pokażmy, że wtedy mamy P(n+ 1), czyli ( n + 1)n(2n+ 1) jest podzielna przez 6. Rzeczywiście, ponieważ

W ten sposób, P(n+ 1) jest uczciwym oświadczeniem, a zatem n(2n 2 - 3n+ 1) jest podzielna przez 6 dla dowolnego n O N.

b) Sprawdź P(1): 6 0 + 3 2 + 3 0 = 11, stąd P(1) jest uczciwym oświadczeniem. Należy udowodnić, że jeśli 6 2 n-2 + 3 n+1 + 3 n-1 jest podzielne przez 11 ( P(n)), następnie 6 2 n + 3 n+2 + 3 n jest również podzielna przez 11 ( P(n+ 1)). Rzeczywiście, ponieważ

6 2n + 3 n+2 + 3 n = 6 2n-2+2 + 3 n+1+1 + 3 n-1+1 == 6 2 6 2 n-2 + 3 3 n+1 + 3 3 n-1 = 3 (6 2 n-2 + 3 n+1 + 3 n-1) + 33 6 2 n-2 i jak 6 2 n-2 + 3 n+1 + 3 n-1 i 33 6 2 n-2 są podzielne przez 11, to ich suma wynosi 6 2n + 3 n+2 + 3 n jest podzielna przez 11. Twierdzenie jest udowodnione. Indukcja w geometrii

Przykład 4 Oblicz stronę prawidłowego 2 n-gon wpisany w okrąg o promieniu R.

Opis bibliograficzny: Badanin AS, Sizova M. Yu Zastosowanie metody indukcji matematycznej do rozwiązywania problemów dotyczących podzielności liczb naturalnych // Młody naukowiec. 2015. №2. S. 84-86..04.2019).

Dość trudne problemy z udowodnieniem podzielności liczb naturalnych są często spotykane w olimpiadach matematycznych. Uczniowie stają przed problemem: jak znaleźć uniwersalną metodę matematyczną, która pozwoli rozwiązać takie problemy?

Okazuje się, że większość problemów podzielności można rozwiązać za pomocą indukcji matematycznej, ale w podręcznikach szkolnych bardzo mało uwagi poświęca się tej metodzie, najczęściej podaje się krótki opis teoretyczny i analizuje się kilka problemów.

Znajdujemy metodę indukcji matematycznej w teorii liczb. U zarania teorii liczb matematycy odkryli wiele faktów indukcyjnie: L. Euler i K. Gauss czasami rozważali tysiące przykładów, zanim zauważyli wzór liczbowy i uwierzyli w niego. Ale jednocześnie zrozumieli, jak mylące mogą być hipotezy, jeśli zdadzą „ostateczny” test. Dla indukcyjnego przejścia od zdania zweryfikowanego dla skończonego podzbioru do podobnego zdania dla całego zbioru nieskończonego potrzebny jest dowód. Metodę tę zaproponował Blaise Pascal, który znalazł ogólny algorytm znajdowania kryteriów podzielności dowolnej liczby całkowitej przez dowolną inną liczbę całkowitą (traktat „O naturze podzielności liczb”).

Metoda indukcji matematycznej służy do udowodnienia przez wnioskowanie prawdziwości pewnego zdania dla wszystkich liczb naturalnych lub prawdziwości zdania rozpoczynającego się od pewnej liczby n.

Rozwiązywanie problemów w celu udowodnienia prawdziwości pewnego stwierdzenia metodą indukcji matematycznej składa się z czterech etapów (ryc. 1):

Ryż. 1. Schemat rozwiązania problemu

1. Podstawa indukcji . Sprawdź poprawność twierdzenia dla najmniejszej liczby naturalnej, dla której to twierdzenie ma sens.

2. Założenie indukcyjne . Zakładamy, że stwierdzenie jest prawdziwe dla pewnej wartości k.

3. przejście indukcyjne . Udowadniamy, że twierdzenie jest prawdziwe dla k+1.

4. Wniosek . Jeżeli taki dowód został zakończony, to na podstawie zasady indukcji matematycznej można argumentować, że twierdzenie to jest prawdziwe dla dowolnej liczby naturalnej n.

Rozważ zastosowanie metody indukcji matematycznej do rozwiązywania problemów w celu udowodnienia podzielności liczb naturalnych.

Przykład 1. Udowodnij, że liczba 5 jest wielokrotnością liczby 19, gdzie n jest liczbą naturalną.

Dowód:

1) Sprawdźmy, czy ten wzór jest prawdziwy dla n = 1: liczba =19 jest wielokrotnością 19.

2) Niech ten wzór będzie prawdziwy dla n = k, tzn. liczba jest wielokrotnością 19.

Podzielna przez 19. Rzeczywiście, pierwszy wyraz jest podzielny przez 19 ze względu na założenie (2); drugi wyraz jest również podzielny przez 19, ponieważ zawiera czynnik 19.

Przykład 2 Wykazać, że suma sześcianów trzech kolejnych liczb naturalnych jest podzielna przez 9.

Dowód:

Udowodnijmy stwierdzenie: „Dla dowolnej liczby naturalnej n wyrażenie n 3 +(n+1) 3 +(n+2) 3 jest wielokrotnością 9.

1) Sprawdź, czy ten wzór jest poprawny dla n = 1: 1 3 +2 3 +3 3 =1+8+27=36 jest wielokrotnością 9.

2) Niech ten wzór będzie prawdziwy dla n = k, tzn. k 3 +(k+1) 3 +(k+2) 3 jest wielokrotnością 9.

3) Udowodnijmy, że wzór jest prawdziwy również dla n = k + 1, czyli (k+1) 3 +(k+2) 3 +(k+3) 3 jest wielokrotnością 9. (k+1) 3 +( k+2) 3 +(k+3) 3 =(k+1) 3 +(k+2) 3 + k 3 + 9k 2 +27 k+ 27=(k 3 +(k+1) 3 +(k +2) 3)+9(k 2 +3k+ 3).

Otrzymane wyrażenie zawiera dwa wyrazy, z których każdy jest podzielny przez 9, więc suma jest podzielna przez 9.

4) Oba warunki zasady indukcji matematycznej są spełnione, zatem twierdzenie jest prawdziwe dla wszystkich wartości n.

Przykład 3 Wykazać, że dla dowolnego naturalnego n liczba 3 2n+1 +2 n+2 jest podzielna przez 7.

Dowód:

1) Sprawdź, czy ten wzór jest poprawny dla n = 1: 3 2*1+1 +2 1+2 = 3 3 +2 3 =35, 35 jest wielokrotnością 7.

2) Niech ten wzór będzie prawdziwy dla n = k, tj. 3 2 k +1 +2 k +2 jest podzielne przez 7.

3) Udowodnijmy, że wzór jest prawdziwy również dla n = k + 1, tj.

3 2(k +1)+1 +2 (k +1)+2 =3 2k +1 3 2 +2k +2 2 1 =3 2k +1 9+2k +2 2 =3 2k +1 9+2 k +2 (9–7)=(3 2 k +1 +2 k +2) 9–7 2 k +2 .T. Ponieważ (3 2 k +1 +2 k +2) 9 jest podzielne przez 7, a 7 2 k +2 jest podzielne przez 7, to ich różnica jest również podzielna przez 7.

4) Oba warunki zasady indukcji matematycznej są spełnione, zatem twierdzenie jest prawdziwe dla wszystkich wartości n.

Wygodne jest rozwiązywanie wielu problemów dowodowych w teorii podzielności liczb naturalnych metodą indukcji matematycznej, można nawet powiedzieć, że rozwiązywanie zadań tą metodą jest dość algorytmiczne, wystarczy wykonać 4 podstawowe kroki. Ale tej metody nie można nazwać uniwersalną, ponieważ są też wady: po pierwsze, można udowodnić tylko na zbiorze liczb naturalnych, a po drugie, można udowodnić tylko dla jednej zmiennej.

Dla rozwoju logicznego myślenia, kultury matematycznej ta metoda jest niezbędnym narzędziem, ponieważ nawet wielki rosyjski matematyk A. N. Kołmogorow powiedział: „Zrozumienie i umiejętność prawidłowego zastosowania zasady indukcji matematycznej jest dobrym kryterium dojrzałości logicznej, która jest absolutnie niezbędne dla matematyki”.

Literatura:

1. Vilenkin N. Ya Indukcja. Kombinatoryka. - M.: Oświecenie, 1976. - 48 s.

2. Genkin L. O indukcji matematycznej. - M., 1962. - 36 s.

3. Solominsky I. S. Metoda indukcji matematycznej. - M.: Nauka, 1974. - 63 s.

4. Sharygin I. F. Fakultatywny kurs z matematyki: Rozwiązywanie problemów: Podręcznik na 10 komórek. Gimnazjum - M.: Oświecenie, 1989. - 252 s.

5. Shen A. Indukcja matematyczna. - M.: MTSNMO, 2007.- 32 s.