Metoda lekcji indukcji matematycznej. Zastosowanie metody indukcji matematycznej do rozwiązywania problemów z podzielności liczb naturalnych

Metoda indukcji matematycznej

Wstęp

Głównym elementem

Indukcja całkowita i niepełna
Zasada indukcji matematycznej
Metoda indukcji matematycznej
Rozwiązanie przykładów
Równość
Podział liczb
nierówności

Wniosek

Spis wykorzystanej literatury

Wstęp

Metody dedukcyjne i indukcyjne są podstawą wszelkich badań matematycznych. Dedukcyjna metoda rozumowania to rozumowanie od ogółu do szczegółu, tj. rozumowania, którego punktem wyjścia jest wynik ogólny, a punktem końcowym wynik szczegółowy. Indukcję stosuje się przy przechodzeniu od wyników szczegółowych do ogólnych, tj. jest przeciwieństwem metody dedukcyjnej.

Metodę indukcji matematycznej można porównać z postępem. Zaczynamy od najniższych, w wyniku logicznego myślenia dochodzimy do najwyższych. Człowiek zawsze dążył do postępu, do umiejętności logicznego rozwijania myśli, co oznacza, że sama natura przeznaczyła go do myślenia indukcyjnego.

Chociaż pole zastosowań metody indukcji matematycznej rozszerzyło się, w szkolnym programie nauczania poświęca się jej niewiele miejsca. Cóż, powiedzmy, że przydatną osobę przyniosą te dwie lub trzy lekcje, za które usłyszy pięć słów teorii, rozwiąże pięć prymitywnych problemów iw rezultacie dostanie piątkę za niewiedzę.

Ale to jest tak ważne - aby móc myśleć indukcyjnie.

Głównym elementem

W swoim pierwotnym znaczeniu słowo „indukcja” odnosi się do rozumowania, za pomocą którego uzyskuje się ogólne wnioski na podstawie szeregu szczegółowych twierdzeń. Najprostszą metodą rozumowania tego rodzaju jest indukcja całkowita. Oto przykład takiego rozumowania.

Niech będzie wymagane ustalenie, że każdą parzystą liczbę naturalną n z przedziału 4 można przedstawić jako sumę dwóch liczb pierwszych. Aby to zrobić, bierzemy wszystkie takie liczby i zapisujemy odpowiednie rozszerzenia:

4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;

14=7+7; 16=11+5; 18=13+5; 20=13+7.

Te dziewięć równości pokazuje, że każda z interesujących nas liczb jest rzeczywiście reprezentowana jako suma dwóch wyrazów pierwszych.

Tak więc pełna indukcja polega na tym, że ogólne stwierdzenie jest udowadniane oddzielnie w każdym ze skończonej liczby możliwych przypadków.

Czasami ogólny wynik można przewidzieć po uwzględnieniu nie wszystkich, ale dużej liczby przypadków szczególnych (tzw. indukcja niezupełna).

Wynik uzyskany przez niezupełną indukcję pozostaje jednak tylko hipotezą, dopóki nie zostanie udowodniony dokładnym rozumowaniem matematycznym, obejmującym wszystkie przypadki szczególne. Innymi słowy, niepełna indukcja w matematyce nie jest uważana za uprawnioną metodę ścisłego dowodu, ale za potężną metodę odkrywania nowych prawd.

Niech na przykład wymagane jest znalezienie sumy pierwszych n kolejnych liczb nieparzystych. Rozważ przypadki szczególne:

1+3+5+7+9=25=5 2

Po rozważeniu tych kilku szczególnych przypadków nasuwa się następujący ogólny wniosek:

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

te. suma pierwszych n kolejnych liczb nieparzystych wynosi n 2

Oczywiście poczyniona obserwacja nie może jeszcze służyć jako dowód słuszności powyższej formuły.

Całkowita indukcja ma tylko ograniczone zastosowanie w matematyce. Wiele interesujących stwierdzeń matematycznych obejmuje nieskończoną liczbę przypadków specjalnych, a nie możemy testować nieskończonej liczby przypadków. Niepełna indukcja często prowadzi do błędnych wyników.

W wielu przypadkach wyjściem z tego rodzaju trudności jest odwołanie się do specjalnej metody rozumowania, zwanej metodą indukcji matematycznej. Jest następująco.

Niech konieczne będzie udowodnienie ważności pewnego stwierdzenia dla dowolnej liczby naturalnej n (na przykład konieczne jest udowodnienie, że suma pierwszych n liczb nieparzystych jest równa n 2). Bezpośrednia weryfikacja tego stwierdzenia dla każdej wartości n jest niemożliwa, ponieważ zbiór liczb naturalnych jest nieskończony. Aby udowodnić to stwierdzenie, najpierw sprawdź jego ważność dla n=1. Następnie okazuje się, że dla dowolnej wartości naturalnej k, ważność rozważanego twierdzenia dla n=k implikuje również jego ważność dla n=k+1.

Wtedy twierdzenie uważa się za udowodnione dla wszystkich n. Rzeczywiście, stwierdzenie jest prawdziwe dla n=1. Ale wtedy jest to również ważne dla następnej liczby n=1+1=2. Ważność twierdzenia dla n=2 implikuje jego ważność dla n=2+

1=3. Oznacza to ważność stwierdzenia dla n=4 i tak dalej. Oczywiste jest, że w końcu dojdziemy do dowolnej liczby naturalnej n. Zatem stwierdzenie jest prawdziwe dla dowolnego n.

Podsumowując to, co zostało powiedziane, formułujemy następującą ogólną zasadę.

Zasada indukcji matematycznej.

Jeśli zdanie A(N) w zależności od liczby naturalnejN, prawda dlaN=1 i z faktu, że jest to prawdziwe dlaN= k (Gdziek-dowolna liczba naturalna), wynika z tego, że jest to również prawdziwe dla następnej liczbyN= k+1, to założenie A(N) jest prawdziwe dla dowolnej liczby naturalnejN.

Jeśli zdanie A(N) jest prawdziwe dlaN= P a jeśli A(k) Þ A(k+1) dla każdegok> P, potem zdanie A(N) jest prawdziwe dla każdegoN> P.

Dowód metodą indukcji matematycznej przeprowadza się w następujący sposób. Najpierw sprawdzane jest twierdzenie, które ma zostać udowodnione, dla n=1, tj. prawdziwość stwierdzenia A(1) jest ustalona. Ta część dowodu nazywana jest podstawą indukcyjną. Po tym następuje część dowodu zwana krokiem indukcyjnym. W tej części udowodniono ważność twierdzenia dla n=k+1 przy założeniu, że twierdzenie jest prawdziwe dla n=k (założenie indukcyjne), tj. udowodnić, że A(k)ÞA(k+1).

PRZYKŁAD 1

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

Rozwiązanie: 1) Mamy n=1=1 2 . Stąd,

stwierdzenie jest prawdziwe dla n=1, tj. A(1) jest prawdziwe.

2) Udowodnijmy, że A(k)ÞA(k+1).

Niech k będzie dowolną liczbą naturalną i niech zdanie będzie prawdziwe dla n=k, tj.

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

Udowodnijmy, że wtedy twierdzenie jest prawdziwe także dla następnej liczby naturalnej n=k+1, tj. Co

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

Rzeczywiście,

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

Więc A(k)ÞA(k+1). Opierając się na zasadzie indukcji matematycznej, dochodzimy do wniosku, że Założenie A(n) jest prawdziwe dla dowolnego nОN.

PRZYKŁAD 2

Udowodnij to

1 + x + x 2 + x 3 + ... + x n \u003d (x n +1 -1) / (x-1), gdzie x¹1

Rozwiązanie: 1) Dla n=1 otrzymujemy

1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1

zatem dla n=1 wzór jest prawdziwy; A(1) jest prawdziwe.

2) Niech k będzie dowolną liczbą naturalną i niech wzór będzie prawdziwy dla n=k, tj.

1 + x + x 2 + x 3 + ... + x k \u003d (x k +1 -1) / (x-1).

Udowodnijmy, że wtedy równość

1 + x + x 2 + x 3 + ... + x k + x k +1 \u003d (x k +2 -1) / (x-1).

Rzeczywiście

1+x+x 2 +x 3 +…+x k +x k +1 =(1+x+x 2 +x 3 +…+x k)+x k +1 =

=(x k +1 -1)/(x-1)+x k +1 =(x k +2 -1)/(x-1).

Więc A(k)ÞA(k+1). Opierając się na zasadzie indukcji matematycznej, dochodzimy do wniosku, że wzór jest prawdziwy dla dowolnej liczby naturalnej n.

PRZYKŁAD 3

Udowodnij, że liczba przekątnych n-kąta wypukłego wynosi n(n-3)/2.

Rozwiązanie: 1) Dla n=3 zdanie jest prawdziwe

A 3 jest poprawne, bo w trójkącie

 A 3 =3(3-3)/2=0 przekątnych;

A 2 A(3) jest prawdziwe.

2) Załóżmy, że w dowolnym

wypukły k-gon ma-

A 1 sya A k \u003d k (k-3) / 2 przekątne.

A k Udowodnijmy, że wtedy w wypukłości

(k+1)-gon liczba

przekątne A k +1 \u003d (k + 1) (k-2) / 2.

Niech А 1 А 2 А 3 …A k A k +1 -wypukły (k+1)-róg. Narysujmy w nim przekątną A 1 A k. Aby policzyć całkowitą liczbę przekątnych tego (k + 1)-gonu, należy policzyć liczbę przekątnych w k-gonie A 1 A 2 ...A k , dodać k-2 do otrzymanej liczby, tj. liczbę przekątnych (k+1)-gon wychodzących z wierzchołka A k +1 , a dodatkowo należy uwzględnić przekątną A 1 A k .

Zatem,

 k +1 =  k +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2.

Więc A(k)ÞA(k+1). Ze względu na zasadę indukcji matematycznej stwierdzenie jest prawdziwe dla dowolnego n-gonu wypukłego.

PRZYKŁAD 4

Udowodnij, że dla dowolnego n zdanie jest prawdziwe:

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

Rozwiązanie: 1) Niech zatem n=1

X 1 \u003d 1 2 \u003d 1 (1 + 1) (2 + 1) / 6 \u003d 1.

Zatem dla n=1 stwierdzenie jest prawdziwe.

2) Załóżmy, że n=k

X k \u003d k 2 \u003d k (k + 1) (2k + 1) / 6.

3) Rozważ to stwierdzenie dla n=k+1

Xk +1 =(k+1)(k+2)(2k+3)/6.

X k +1 =1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =k(k+1)(2k+1)/6+ +(k+1) 2 =(k (k+1)(2k+1)+6(k+1) 2)/6=(k+1)(k(2k+1)+

6(k+1))/6=(k+1)(2k 2 +7k+6)/6=(k+1)(2(k+3/2)(k+

2))/6=(k+1)(k+2)(2k+3)/6.

Udowodniliśmy słuszność równości dla n=k+1, zatem na mocy metody indukcji matematycznej stwierdzenie jest prawdziwe dla każdego naturalnego n.

PRZYKŁAD 5

Udowodnij, że dla dowolnego naturalnego n równość jest prawdziwa:

1 3 +2 3 +3 3 +…+n 3 = n 2 (n+1) 2 /4.

Rozwiązanie: 1) Niech n=1.

Wtedy X 1 =1 3 =1 2 (1+1) 2 /4=1.

Widzimy, że dla n=1 stwierdzenie jest prawdziwe.

2) Załóżmy, że równość jest prawdziwa dla n=k

X k \u003d k 2 (k + 1) 2/4.

3) Udowodnijmy prawdziwość tego stwierdzenia dla n=k+1, tj.

X k+1 =(k+1) 2 (k+2) 2 /4. X k+1 =1 3 +2 3 +…+k 3 +(k+1) 3 =k 2 (k+1) 2 /4+(k+1) 3 =(k 2 (k++1) 2 +4(k+1) 3)/4=(k+1) 2 (k 2 +4k+4)/4=(k+1) 2 (k+2) 2 /4.

Z powyższego dowodu jasno wynika, że stwierdzenie jest prawdziwe dla n=k+1, zatem równość jest prawdziwa dla dowolnego naturalnego n.

PRZYKŁAD 6

Udowodnij to

((2 3 +1)/(2 3 -1))´((3 3 +1)/(3 3 -1))´…´((n 3 +1)/(n 3 -1))= 3n(n+1)/2(n2+n+1), gdzie n>2.

Rozwiązanie: 1) Dla n=2 tożsamość wygląda następująco: (2 3 +1)/(2 3 -1)=(3´2´3)/2(2 2 +2+1),

te. jest poprawna.

2) Załóżmy, że wyrażenie jest prawdziwe dla n=k

(2 3 +1)/(2 3 -1)´…´(k 3 +1)/(k 3 -1)=3k(k+1)/2(k 2 +k+1).

3) Udowodnimy poprawność wyrażenia dla n=k+1.

(((2 3 +1)/(2 3 -1))´…´((k 3 +1)/(k 3 -1)))´(((k+1) 3 +

1)/((k+1) 3 -1))=(3k(k+1)/2(k 2 +k+1))´((k+2)((k+

1) 2 -(k+1)+1)/k((k+1) 2 +(k+1)+1))=3(k+1)(k+2)/2´

´((k+1) 2 +(k+1)+1).

Udowodniliśmy słuszność równości dla n=k+1, zatem ze względu na metodę indukcji matematycznej stwierdzenie jest prawdziwe dla dowolnego n>2

PRZYKŁAD 7

Udowodnij to

1 3 -2 3 +3 3 -4 3 +…+(2n-1) 3 -(2n) 3 =-n 2 (4n+3)

dla dowolnego naturalnego n .

Rozwiązanie: 1) Niech zatem n=1

1 3 -2 3 =-1 3 (4+3); -7=-7.

2) Załóżmy zatem, że n=k

1 3 -2 3 +3 3 -4 3 +…+(2k-1) 3 -(2k) 3 =-k 2 (4k+3).

3) Udowodnijmy prawdziwość tego stwierdzenia dla n=k+1

(1 3 -2 3 +…+(2k-1) 3 -(2k) 3)+(2k+1) 3 -(2k+2) 3 =-k 2 (4k+3)+

+(2k+1) 3 -(2k+2) 3 =-(k+1) 3 (4(k+1)+3).

Udowodniono również słuszność równości dla n=k+1, więc stwierdzenie jest prawdziwe dla dowolnej liczby naturalnej n.

PRZYKŁAD 8

Udowodnij ważność tożsamości

(1 2 /1´3)+(2 2 /3´5)+…+(n 2 /(2n-1)´(2n+1))=n(n+1)/2(2n+1)

dla dowolnego naturalnego n .

1) Dla n=1 tożsamość jest prawdziwa 1 2 /1´3=1(1+1)/2(2+1).

2) Załóżmy, że dla n=k

(1 2 /1´3)+…+(k 2 /(2k-1)´(2k+1))=k(k+1)/2(2k+1).

3) Udowodnijmy, że tożsamość jest prawdziwa dla n=k+1.

(1 2 /1´3)+…+(k 2 /(2k-1)(2k+1))+(k+1) 2 /(2k+1)(2k+3)=(k(k+ 1) )/2(2k+1))+((k+1) 2 /(2k+1)(2k+3))=((k+1)/(2k+1))´((k/2 ) +((k+1)/(2k+3)))=(k+1)(k+2)´ (2k+1)/2(2k+1)(2k+3)=(k+1 ) (k+2)/2(2(k+1)+1).

Z powyższego dowodu widać, że twierdzenie jest prawdziwe dla dowolnej liczby naturalnej n.

PRZYKŁAD 9

Udowodnij, że (11 n+2 +12 2n+1) jest podzielne przez 133 bez reszty.

Rozwiązanie: 1) Niech zatem n=1

11 3 +12 3 \u003d (11 + 12) (11 2 -132 + 12 2) \u003d 23´133.

Ale (23´133) jest podzielne przez 133 bez reszty, więc dla n=1 stwierdzenie jest prawdziwe; A(1) jest prawdziwe.

2) Załóżmy, że (11 k+2 +12 2k+1) jest podzielne przez 133 bez reszty.

3) Udowodnijmy to w tym przypadku

(11 k+3 +12 2k+3) dzieli się przez 133 bez reszty. Rzeczywiście, 11 k +3 +12 2k+3 =11´11 k+2 +12 2 ´12 2k+1 =11´11 k+2 +

+(11+133)´12 2k+1 =11(11k+2 +12 2k+1)+133´12 2k+1 .

Otrzymana suma jest podzielna przez 133 bez reszty, ponieważ jej pierwszy wyraz jest podzielny przez 133 bez reszty z założenia, aw drugim czynniku jest 133. Zatem A(k)ÞА(k+1). Za pomocą metody indukcji matematycznej twierdzenie jest udowodnione.

PRZYKŁAD 10

Udowodnij, że dla dowolnego n 7 n -1 jest podzielne przez 6 bez reszty.

Rozwiązanie: 1) Niech n=1, wtedy X 1 =7 1 -1=6 dzieli się przez 6 bez reszty. Zatem dla n=1 stwierdzenie jest prawdziwe.

2) Załóżmy, że dla n=k

7 k -1 dzieli się przez 6 bez reszty.

3) Udowodnijmy, że stwierdzenie jest prawdziwe dla n=k+1.

X k+1 =7 k+1 -1=7´7 k -7+6=7(7 k -1)+6.

Pierwszy wyraz jest podzielny przez 6, ponieważ 7 k -1 jest podzielne przez 6 z założenia, a drugi wyraz to 6. Więc 7 n -1 jest wielokrotnością 6 dla dowolnego naturalnego n. Za pomocą metody indukcji matematycznej twierdzenie jest udowodnione.

PRZYKŁAD 11

Udowodnij, że 3 3n-1 +2 4n-3 dla dowolnego naturalnego n jest podzielne przez 11.
Rozwiązanie: 1) Niech zatem n=1

X 1 \u003d 3 3-1 +2 4-3 \u003d 3 2 +2 1 \u003d 11 dzieli się przez 11 bez reszty. Zatem dla n=1 stwierdzenie jest prawdziwe.

2) Załóżmy, że dla n=k

X k \u003d 3 3k-1 +2 4k-3 jest podzielne przez 11 bez reszty.

3) Udowodnijmy, że stwierdzenie jest prawdziwe dla n=k+1.

X k+1 =3 3(k+1)-1 +2 4(k+1)-3 =3 3k+2 +2 4k+1 =3 3 ´3 3k-1 +2 4 ´2 4k-3 =

27´3 3k-1 +16´2 4k-3 =(16+11)´3 3k-1 +16´2 4k-3 =16´3 3k-1 +

11´3 3k-1 +16´2 4k-3 =16(3 3k-1 +2 4k-3)+11´3 3k-1 .

Pierwszy wyraz jest podzielny przez 11 bez reszty, ponieważ 3 3 k-1 +2 4k-3 jest z założenia podzielny przez 11, drugi wyraz jest podzielny przez 11, ponieważ jednym z jego dzielników jest liczba 11. Zatem suma wynosi podzielna przez 11 bez reszty dla dowolnego naturalnego n. Za pomocą metody indukcji matematycznej twierdzenie jest udowodnione.

PRZYKŁAD 12

Udowodnij, że 11 2n -1 dla dowolnej liczby całkowitej dodatniej n jest podzielne przez 6 bez reszty.

Rozwiązanie: 1) Niech n=1, to 11 2 -1=120 jest podzielne przez 6 bez reszty. Zatem dla n=1 stwierdzenie jest prawdziwe.

2) Załóżmy, że dla n=k

11 2 k -1 dzieli się przez 6 bez reszty.

11 2(k+1) -1=121´11 2k -1=120´11 2k +(11 2k -1).

Oba wyrazy są podzielne przez 6 bez reszty: pierwszy zawiera wielokrotność 6 liczby 120, a drugi jest podzielny przez 6 bez reszty z założenia. Zatem suma jest podzielna przez 6 bez reszty. Za pomocą metody indukcji matematycznej twierdzenie jest udowodnione.

PRZYKŁAD 13

Udowodnij, że 3 3 n+3 -26n-27 dla dowolnej dodatniej liczby całkowitej n jest podzielne przez 26 2 (676) bez reszty.

Rozwiązanie: Najpierw udowodnijmy, że 3 3 n+3 -1 jest podzielne przez 26 bez reszty.

Dla n=0

3 3 -1=26 jest podzielne przez 26

Załóżmy, że dla n=k

3 3k+3 -1 dzieli się przez 26

Udowodnijmy, że stwierdzenie

prawda dla n=k+1.

3 3 k+6 -1=27´3 3k+3 -1=26´3 3k+3 +(3 3 k +3 -1) - dzieli się przez 26

Udowodnijmy teraz twierdzenie sformułowane w warunku problemu.

1) Jest oczywiste, że dla n=1 stwierdzenie jest prawdziwe

3 3+3 -26-27=676

2) Załóżmy, że dla n=k

wyrażenie 3 3 k+3 -26k-27 jest podzielne przez 26 2 bez reszty.

3) Udowodnijmy, że stwierdzenie jest prawdziwe dla n=k+1

3 3k+6 -26(k+1)-27=26(3 3k+3 -1)+(3 3k+3 -26k-27).

Oba wyrazy są podzielne przez 26 2 ; pierwszy jest podzielny przez 26 2, ponieważ udowodniliśmy, że wyrażenie w nawiasie jest podzielne przez 26, a drugi jest podzielny przez hipotezę indukcyjną. Za pomocą metody indukcji matematycznej twierdzenie jest udowodnione.

PRZYKŁAD 14

Udowodnij, że jeśli n>2 i x>0, to nierówność

(1+x) n >1+n´x.

Rozwiązanie: 1) Dla n=2 nierówność jest prawdziwa, ponieważ

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

Zatem A(2) jest prawdziwe.

2) Udowodnijmy, że A(k)ÞA(k+1) jeśli k> 2. Załóżmy, że A(k) jest prawdziwe, tj. że nierówność

(1+x) k >1+k´x. (3)

Udowodnijmy, że wtedy A(k+1) jest również prawdziwe, tj. że nierówność

(1+x) k+1 >1+(k+1)´x.

Rzeczywiście, mnożąc obie strony nierówności (3) przez liczbę dodatnią 1+x, otrzymujemy

(1+x) k+1 >(1+k´x)(1+x).

Rozważ prawą stronę ostatniej nierównej

stva; mamy

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

W rezultacie otrzymujemy to

(1+x) k+1 >1+(k+1)´x.

Więc A(k)ÞA(k+1). Opierając się na zasadzie indukcji matematycznej, można argumentować, że nierówność Bernoulliego jest ważna dla każdego

PRZYKŁAD 15

Udowodnij, że nierówność jest prawdziwa

(1+a+a 2) m > 1+m´a+(m(m+1)/2)´a 2 dla a> 0.

Rozwiązanie: 1) Dla m=1

(1+a+a 2) 1 > 1+a+(2/2)´a 2 obie części są równe.

2) Załóżmy, że dla m=k

(1+a+a 2) k >1+k´a+(k(k+1)/2)´a 2

3) Udowodnijmy, że dla m=k+1 nierówność jest prawdziwa

(1+a+a 2) k+1 =(1+a+a 2)(1+a+a 2) k >(1+a+a 2)(1+k´a+

+(k(k+1)/2)´a 2)=1+(k+1)´a+((k(k+1)/2)+k+1)´a 2 +

+((k(k+1)/2)+k)´a 3 +(k(k+1)/2)´a 4 > 1+(k+1)´a+

+((k+1)(k+2)/2)´a 2 .

Udowodniliśmy słuszność nierówności dla m=k+1, zatem na mocy metody indukcji matematycznej nierówność jest prawdziwa dla dowolnego naturalnego m.

PRZYKŁAD 16

Udowodnij, że dla n>6 nierówność

Rozwiązanie: Przepiszmy nierówność w formie

Dla n=7 mamy

3 7 /2 7 =2187/128>14=2´7

nierówność jest prawdziwa.

Załóżmy, że dla n=k

3) Udowodnijmy poprawność nierówności dla n=k+1.

3k+1 /2k+1 =(3k /2k)´(3/2)>2k´(3/2)=3k>2(k+1).

Ponieważ k>7, ostatnia nierówność jest oczywista.

Dzięki metodzie indukcji matematycznej nierówność jest ważna dla dowolnego naturalnego n.

PRZYKŁAD 17

Udowodnij, że dla n>2 nierówność

1+(1/2 2)+(1/3 2)+…+(1/n 2)

Rozwiązanie: 1) Dla n=3 nierówność jest prawdziwa

1+(1/2 2)+(1/3 2)=245/180

Załóżmy, że dla n=k

1+(1/2 2)+(1/3 2)+…+(1/k 2)=1,7-(1/k).

3) Udowodnimy zasadność nie-

równości dla n=k+1

(1+(1/2 2)+…+(1/k 2))+(1/(k+1) 2)

Udowodnijmy, że 1,7-(1/k)+(1/(k+1) 2)

Û(1/(k+1) 2)+(1/k+1)Ûk(k+2)

To ostatnie jest oczywiste, a zatem

1+(1/2 2)+(1/3 2)+…+(1/(k+1) 2)

Za pomocą metody indukcji matematycznej udowodniono nierówność.

Wniosek

W szczególności, studiując metodę indukcji matematycznej, poprawiłem swoją wiedzę w tej dziedzinie matematyki, a także nauczyłem się rozwiązywać problemy, które wcześniej były poza moją mocą.

Zasadniczo były to logiczne i zabawne zadania, tj. tylko takie, które zwiększają zainteresowanie samą matematyką jako nauką. Rozwiązywanie takich problemów staje się rozrywką i może przyciągać do matematycznych labiryntów coraz więcej dociekliwych osób. Moim zdaniem jest to podstawa każdej nauki.

Kontynuując badanie metody indukcji matematycznej, postaram się nauczyć, jak zastosować ją nie tylko w matematyce, ale także w rozwiązywaniu problemów z fizyki, chemii i samego życia.

MATEMATYKA:

WYKŁADY, ZADANIA, ROZWIĄZANIA

Podręcznik / VG Boltyansky, Yu. V. Sidorov, M. I. Shabunin. Potpourri LLC 1996.

ALGEBRA I ZASADY ANALIZY

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

Indukcja jest metodą uzyskiwania ogólnego stwierdzenia z poszczególnych obserwacji. W przypadku, gdy stwierdzenie matematyczne dotyczy skończonej liczby obiektów, można je udowodnić, sprawdzając każdy obiekt. Na przykład stwierdzenie: „Każda dwucyfrowa liczba parzysta jest sumą dwóch liczb pierwszych” wynika z szeregu równości, których ustalenie jest całkiem realistyczne:

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

Metoda dowodu, w której twierdzenie jest weryfikowane dla skończonej liczby przypadków, wyczerpujących wszystkie możliwości, nazywana jest indukcją zupełną. Ta metoda ma stosunkowo rzadkie zastosowanie, ponieważ stwierdzenia matematyczne z reguły dotyczą nie skończonych, ale nieskończonych zbiorów obiektów. Na przykład stwierdzenie o liczbach parzystych dwucyfrowych udowodnione powyżej przez całkowitą indukcję jest tylko szczególnym przypadkiem twierdzenia: „Każda liczba parzysta jest sumą dwóch liczb pierwszych”. To twierdzenie nie zostało jeszcze udowodnione ani obalone.

Indukcja matematyczna to metoda dowodzenia pewnego twierdzenia dla dowolnego naturalnego n oparta na zasadzie indukcji matematycznej: „Jeżeli twierdzenie jest prawdziwe dla n=1 i z jego ważności dla n=k wynika, że twierdzenie to jest prawdziwe dla n= k+1, to jest prawdziwe dla wszystkich n”. Metoda dowodu przez indukcję matematyczną jest następująca:

1) podstawa indukcji: udowodnić lub bezpośrednio zweryfikować poprawność twierdzenia dla n=1 (czasem n=0 lub n=n 0);

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

Problemy z rozwiązaniami

1. Udowodnij, że dla dowolnego naturalnego n liczba 3 2n+1 +2 n+2 jest podzielna przez 7.

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

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

Hipoteza indukcyjna. Niech A(k) będzie podzielne przez 7.

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

А(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 ZA(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 dowolnego naturalnego n.

2. Wykaż, że dla dowolnej dodatniej liczby całkowitej n liczba 2 3 n +1 jest podzielna przez 3 n+1 i nie jest podzielna przez 3 n+2 .

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

Dla n=1 mamy, a 1 =2 3 +1=9. Zatem 1 jest podzielne przez 3 2 i niepodzielne przez 3 3 .

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

i 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 m ((2 3 k +1) 2 –3 2 3 k)=3 k+1 m ((3 k+1 m) 2 –3 2 3 k)=

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

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

Dlatego twierdzenie jest udowodnione dla dowolnego naturalnego n .

3. Wiadomo, że x+1/x jest liczbą całkowitą. Udowodnij, że х n +1/х n jest również liczbą całkowitą dla dowolnej liczby całkowitej n.

Wprowadźmy notację: a i \u003d x i +1 / x i i od razu zauważmy, że a i \u003d a -i, więc będziemy nadal mówić o indeksach naturalnych.

Uwaga: a 1 jest liczbą całkowitą według warunku; a 2 jest liczbą całkowitą, ponieważ a 2 \u003d (a 1) 2 -2; i 0=2.

Załóżmy, że k jest liczbą całkowitą dla dowolnej dodatniej liczby całkowitej 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 i n – 1 jest liczbą całkowitą zgodnie z hipotezą indukcyjną. Zatem à n+1 jest również liczbą całkowitą. Zatem х n +1/х n jest liczbą całkowitą dla dowolnej liczby całkowitej n, co należało udowodnić.

4. Udowodnij, że dla dowolnej dodatniej liczby całkowitej n większej od 1 zachodzi podwójna nierówność

5. Udowodnij, że dla naturalnych n > 1 i |х|

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

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

(1–x) 2 + (1 + x) 2 \u003d 2 + 2 x 2

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

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

Nierówność jest udowodniona dla dowolnej liczby naturalnej n > 1.

6. Na 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.

Skorzystajmy z metody indukcji matematycznej.

Dla n=1 twierdzenie jest oczywiste.

Załóżmy, że stwierdzenie jest prawdziwe dla dowolnej mapy utworzonej przez n okręgów i niech n + 1 okręgów będzie danych na płaszczyźnie. Usuwając jedno z tych kół, otrzymujemy mapę, którą zgodnie z przyjętym założeniem można poprawnie pokolorować dwoma kolorami (patrz pierwszy rysunek poniżej).

Następnie przywracamy odrzucone koło i po jednej stronie, na przykład wewnątrz, zmieniamy kolor każdego obszaru na przeciwny (patrz drugi rysunek). Łatwo zauważyć, że w tym przypadku otrzymamy mapę poprawnie pokolorowaną dwoma kolorami, ale dopiero teraz z n + 1 okręgami, co należało udowodnić.

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

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

2) dowolne dwa sąsiednie wierzchołki są pomalowane na różne kolory;

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

Udowodnij, że każdy piękny n-kąt można podzielić na „piękne” trójkąty za pomocą nieprzecinających się przekątnych.

Skorzystajmy z metody indukcji matematycznej.

podstawa indukcji. Dla najmniejszego możliwego n=3 sformułowanie problemu jest oczywiste: wierzchołki „pięknego” trójkąta są pomalowane na trzy różne kolory i żadne cięcia nie są potrzebne.

Hipoteza indukcyjna. 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, stosując hipotezę indukcyjną, że można go podzielić pewnymi przekątnymi na „piękne” trójkąty. Oznaczmy przez А 1 , А 2 , А 3 , … А n , А n+1 – kolejne wierzchołki (n+1)-gonu. Jeśli tylko jeden wierzchołek (n + 1)-gon jest pokolorowany na którykolwiek z trzech kolorów, to łącząc ten wierzchołek przekątnymi ze wszystkimi niesąsiadującymi z nim wierzchołkami, otrzymujemy niezbędny podział (n + 1)- w „piękne” trójkąty.

Jeżeli co najmniej dwa wierzchołki kąta (n + 1)-gon są pomalowane na każdy z trzech kolorów, to kolor wierzchołka A 1 oznaczamy liczbą 1, a kolor wierzchołka A 2 liczbą 2 . Niech k będzie najmniejszą liczbą taką, że wierzchołek Ak jest pokolorowany na trzeci kolor. Wiadomo, że k > 2. Odetnijmy trójkąt € k–2 € k–1 € k od (n+1)-gonu o przekątnej € k–2 € k . Zgodnie z wyborem liczby k wszystkie wierzchołki tego trójkąta są pomalowane na trzy różne kolory, czyli trójkąt ten 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 pozostaje, również będzie z powodu założenia indukcyjnego „piękny”, tzn. dzieli się na „piękne” trójkąty, co i trzeba było udowodnić.

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

Przeprowadźmy dowód 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 dwie z nich miały wspólny punkt. Dla n = 3 twierdzenie jest oczywiste. Załóżmy, że to twierdzenie jest prawdziwe dla dowolnego n-gonu i na jego podstawie udowodnijmy jego ważność dla dowolnego (n + 1)-gonu.

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

Odrzucając punkt C wraz z przekątną CA, otrzymujemy n-kąt wypukły, w którym wybrano więcej niż n boków i przekątnych, z których dowolne dwie mają wspólny punkt. W ten sposób dochodzimy do sprzeczności z założeniem, że twierdzenie jest prawdziwe dla dowolnego wypukłego n-gonu.

Zatem dla (n + 1)-gon stwierdzenie jest prawdziwe. Zgodnie z zasadą indukcji matematycznej stwierdzenie jest prawdziwe dla dowolnego n-gonu wypukłego.

9. Na płaszczyźnie poprowadzono n linii, 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ę.

Za pomocą elementarnych rysunków łatwo jest upewnić się, że jedna prosta dzieli płaszczyznę na 2 części, dwie proste na 4 części, trzy proste na 7 części, a cztery proste na 11 części.

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

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, co łatwo ustalić, używając wzoru na sumę pierwszych n wyrazów ciągu arytmetycznego,

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

Udowodnijmy słuszność tego wzoru metodą indukcji matematycznej.

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

Po przyjęciu założenia indukcyjnego rozważ k + 1 prostych spełniających warunek problemu. Dowolnie wybieramy z nich k prostych. Zgodnie z hipotezą indukcyjną dzielą płaszczyznę na 1+ k(k+1)/2 części. Pozostała (k + 1)-ta linia zostanie podzielona wybranymi k liniami na k + 1 części, a zatem przejdzie przez (k + 1)-tą część, na którą płaszczyzna została już podzielona, a każda z części te zostaną podzielone na 2 części, to znaczy zostanie dodanych k+1 części więcej. 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 wstawia się nawiasy wskazujące kolejność działań, a wynik zapisuje się w postaci ułamka:

(w tym przypadku każda z liter x 1, x 2, ..., x n jest albo w liczniku ułamka, albo w mianowniku). Ile różnych wyrażeń można w ten sposób otrzymać przy wszystkich możliwych sposobach ułożenia nawiasów?

Przede wszystkim jasne jest, że w wynikowym ułamku x 1 będzie w liczniku. Niemal równie oczywiste jest, że x 2 będzie w mianowniku dowolnego układu nawiasów (znak dzielenia przed x 2 odnosi się albo do samego x 2, albo do dowolnego wyrażenia zawierającego x 2 w liczniku).

Można przyjąć, że wszystkie inne litery x 3 , x 4 , ... , x n mogą znajdować się w liczniku lub mianowniku w sposób całkowicie dowolny. Wynika z tego, że w sumie można otrzymać 2 n-2 ułamki: każda z n-2 liter x 3, x 4, ..., x n może być niezależnie od pozostałych w liczniku lub mianowniku.

Udowodnijmy to twierdzenie przez indukcję.

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

więc zdanie jest prawdziwe.

Zakładamy, że jest ona prawdziwa dla n=k i udowadniamy dla n=k+1.

Niech wyrażenie x 1: x 2: ...: x k, po pewnym układzie nawiasów, będzie zapisane jako ułamek Q. Jeśli x k: x k+1 zostanie podstawione w tym wyrażeniu zamiast x k, to x k będzie w to samo miejsce, co było we ułamkach Q, a x k + 1 nie będzie tam, gdzie stało x k (jeśli x k było w mianowniku, to x k + 1 będzie w liczniku i odwrotnie).

Teraz udowodnijmy, że możemy dodać x k+1 w to samo miejsce co x k . W ułamku Q, po umieszczeniu nawiasów, koniecznie będzie wyrażenie postaci q:x k, gdzie q to litera x k–1 lub jakieś wyrażenie 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 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 twierdzenie jest udowodnione.

Odpowiedź: 2 ułamki n-2.

Problemy bez rozwiązań

1. Udowodnij, ż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;

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

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

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

4. Znajdź liczby naturalne a, b, c niepodzielne 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.

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

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

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

Metodę indukcji matematycznej odnajdujemy w teorii liczb. U zarania teorii liczb matematycy odkrywali 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 przejdą „ostateczny” test. Do indukcyjnego przejścia od stwierdzenia zweryfikowanego dla skończonego podzbioru do podobnego stwierdzenia dla całego zbioru nieskończonego potrzebny jest dowód. Metodę tę zaproponował Blaise Pascal, który znalazł ogólny algorytm znajdowania znaków podzielności dowolnej liczby całkowitej przez dowolną inną liczbę całkowitą (traktat „O naturze podzielności liczb”).

Metodę indukcji matematycznej stosuje się do udowodnienia przez rozumowanie 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 twierdzenie ma sens.

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

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

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

Rozważ zastosowanie metody indukcji matematycznej do rozwiązywania problemów, aby udowodnić podzielność 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 ta formuła jest prawdziwa dla n = 1: liczba =19 jest wielokrotnością liczby 19.

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

Podzielny przez 19. Rzeczywiście, pierwszy wyraz jest podzielny przez 19 z powodu założenia (2); drugi wyraz jest również podzielny przez 19, ponieważ zawiera współczynnik 19.

Przykład 2 Udowodnij, ż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, tj. 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, tj. (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).

Wynikowe 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, dlatego teza jest prawdziwa dla wszystkich wartości n.

Przykład 3 Udowodnij, ż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 2 k +1 3 2 +2 k +2 2 1 =3 2 k +1 9+2 k +2 2 =3 2 k +1 9+2 k +2 (9–7)=(3 2 k +1 +2 k +2) 9–7 2 k +2 .T. Skoro (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, dlatego teza jest prawdziwa dla wszystkich wartości n.

Wiele problemów dowodowych w teorii podzielności liczb naturalnych rozwiązuje się wygodnie metodą indukcji matematycznej, można nawet powiedzieć, że rozwiązywanie problemów 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 konieczne 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 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.

Wstęp

Głównym elementem

1. Indukcja całkowita i niepełna

2. Zasada indukcji matematycznej

3. Metoda indukcji matematycznej

4. Rozwiązanie przykładów

5. Równości

6. Dzielenie liczb

7. Nierówności

Wniosek

Spis wykorzystanej literatury

Wstęp

Ale to jest tak ważne - aby móc myśleć indukcyjnie.

Głównym elementem

Niech będzie wymagane ustalenie, że każda naturalna liczba parzysta n w obrębie 4< n < 20 представимо в виде суммы двух простых чисел. Для этого возьмём все такие числа и выпишем соответствующие разложения:

4=2+2; 6=3+3; 8=5+3; 10=7+3; 12=7+5;

14=7+7; 16=11+5; 18=13+5; 20=13+7.

Te dziewięć równości pokazuje, że każda z interesujących nas liczb jest rzeczywiście reprezentowana jako suma dwóch wyrazów pierwszych.

Tak więc pełna indukcja polega na tym, że ogólne stwierdzenie jest udowadniane oddzielnie w każdym ze skończonej liczby możliwych przypadków.

Czasami ogólny wynik można przewidzieć po uwzględnieniu nie wszystkich, ale dużej liczby przypadków szczególnych (tzw. indukcja niezupełna).

Niech na przykład wymagane jest znalezienie sumy pierwszych n kolejnych liczb nieparzystych. Rozważ przypadki szczególne:

1+3+5+7+9=25=5 2

Po rozważeniu tych kilku szczególnych przypadków nasuwa się następujący ogólny wniosek:

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

te. suma pierwszych n kolejnych liczb nieparzystych wynosi n 2

Oczywiście poczyniona obserwacja nie może jeszcze służyć jako dowód słuszności powyższej formuły.

W wielu przypadkach wyjściem z tego rodzaju trudności jest odwołanie się do specjalnej metody rozumowania, zwanej metodą indukcji matematycznej. Jest następująco.

1=3. Oznacza to ważność stwierdzenia dla n=4 i tak dalej. Oczywiste jest, że w końcu dojdziemy do dowolnej liczby naturalnej n. Zatem stwierdzenie jest prawdziwe dla dowolnego n.

Podsumowując to, co zostało powiedziane, formułujemy następującą ogólną zasadę.

Zasada indukcji matematycznej.

Jeśli zdanie A( N ) w zależności od liczby naturalnej N , prawda dla N =1 i z faktu, że jest to prawdziwe dla n=k (Gdzie k -dowolna liczba naturalna), wynika z tego, że jest to również prawdziwe dla następnej liczby n=k+1 , to założenie A( N ) jest prawdziwe dla dowolnej liczby naturalnej N .

W wielu przypadkach może być konieczne udowodnienie ważności pewnego stwierdzenia nie dla wszystkich liczb naturalnych, ale tylko dla n>p, gdzie p jest ustaloną liczbą naturalną. W tym przypadku zasada indukcji matematycznej jest sformułowana w następujący sposób. Jeśli zdanie A( N ) jest prawdziwe dla n=p a jeśli A( k ) Þ A( k+1) dla kazdego k>p, wtedy zdanie A( N) prawdziwe dla nikogo n>str.

PRZYKŁAD 1

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

Rozwiązanie: 1) Mamy n=1=1 2 . Stąd,

stwierdzenie jest prawdziwe dla n=1, tj. A(1) jest prawdziwe.

2) Udowodnijmy, że A(k)ÞA(k+1).

Niech k będzie dowolną liczbą naturalną i niech zdanie będzie prawdziwe dla n=k, tj.

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

Udowodnijmy, że wtedy twierdzenie jest prawdziwe także dla następnej liczby naturalnej n=k+1, tj. Co

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

Rzeczywiście,

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

Więc A(k)ÞA(k+1). Opierając się na zasadzie indukcji matematycznej, dochodzimy do wniosku, że Założenie A(n) jest prawdziwe dla dowolnego nОN.

PRZYKŁAD 2

Udowodnij to

1+x+x 2 +x 3 +…+x n =(x n+1 -1)/(x-1), gdzie x¹1

Rozwiązanie: 1) Dla n=1 otrzymujemy

1+x=(x 2 -1)/(x-1)=(x-1)(x+1)/(x-1)=x+1

zatem dla n=1 wzór jest prawdziwy; A(1) jest prawdziwe.

2) Niech k będzie dowolną liczbą naturalną i niech wzór będzie prawdziwy dla n=k, tj.

1 + x + x 2 + x 3 + ... + x k \u003d (x k + 1 -1) / (x-1).

Udowodnijmy, że wtedy równość

1+x+x 2 +x 3 +…+x k +x k+1 =(x k+2 -1)/(x-1).

Rzeczywiście

1+х+х 2 +x 3 +…+х k +x k+1 =(1+x+x 2 +x 3 +…+x k)+x k+1 =

=(x k+1 -1)/(x-1)+x k+1 =(x k+2 -1)/(x-1).

Więc A(k)ÞA(k+1). Opierając się na zasadzie indukcji matematycznej, dochodzimy do wniosku, że wzór jest prawdziwy dla dowolnej liczby naturalnej n.

PRZYKŁAD 3

Udowodnij, że liczba przekątnych n-kąta wypukłego wynosi n(n-3)/2.

Rozwiązanie: 1) Dla n=3 zdanie jest prawdziwe

A 3 jest poprawne, bo w trójkącie

 A 3 =3(3-3)/2=0 przekątnych;

A 2 A(3) jest prawdziwe.

2) Załóżmy, że w dowolnym

wypukły k-gon ma-

A 1 sya A k \u003d k (k-3) / 2 przekątne.

A k Udowodnijmy, że wtedy w wypukłości

(k+1)-gon liczba

przekątne A k+1 =(k+1)(k-2)/2.

Niech А 1 А 2 А 3 …A k A k+1 -kąt wypukły (k+1). Narysujmy w nim przekątną A 1 A k. Aby policzyć całkowitą liczbę przekątnych tego (k + 1)-gonu, należy policzyć liczbę przekątnych w k-gonie A 1 A 2 ...A k , dodać k-2 do otrzymanej liczby, tj. liczbę przekątnych (k+1)-gon wychodzących z wierzchołka A k+1 , a dodatkowo należy uwzględnić przekątną A 1 Ak.

Zatem,

 k+1 = k +(k-2)+1=k(k-3)/2+k-1=(k+1)(k-2)/2.

Więc A(k)ÞA(k+1). Ze względu na zasadę indukcji matematycznej stwierdzenie jest prawdziwe dla dowolnego n-gonu wypukłego.

PRZYKŁAD 4

Udowodnij, że dla dowolnego n zdanie jest prawdziwe:

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

Rozwiązanie: 1) Niech zatem n=1

X 1 \u003d 1 2 \u003d 1 (1 + 1) (2 + 1) / 6 \u003d 1.

Zatem dla n=1 stwierdzenie jest prawdziwe.

2) Załóżmy, że n=k

X k \u003d k 2 \u003d k (k + 1) (2k + 1) / 6.

3) Rozważ to stwierdzenie dla n=k+1

Xk+1 =(k+1)(k+2)(2k+3)/6.

X k+1 =1 2 +2 2 +3 2 +…+k 2 +(k+1) 2 =k(k+1)(2k+1)/6+ +(k+1) 2 =(k (k+1)(2k+1)+6(k+1) 2)/6=(k+1)(k(2k+1)+

6(k+1))/6=(k+1)(2k 2 +7k+6)/6=(k+1)(2(k+3/2)(k+

2))/6=(k+1)(k+2)(2k+3)/6.

Udowodniliśmy słuszność równości dla n=k+1, zatem na mocy metody indukcji matematycznej stwierdzenie jest prawdziwe dla każdego naturalnego n.

PRZYKŁAD 5

Udowodnij, że dla dowolnego naturalnego n równość jest prawdziwa:

1 3 +2 3 +3 3 +…+n 3 = n 2 (n+1) 2 /4.

Rozwiązanie: 1) Niech n=1.

Wtedy X 1 =1 3 =1 2 (1+1) 2 /4=1.

Widzimy, że dla n=1 stwierdzenie jest prawdziwe.

2) Załóżmy, że równość jest prawdziwa dla n=k

Wykład 6. Metoda indukcji matematycznej.

Nową wiedzę w nauce i życiu zdobywa się na różne sposoby, ale wszystkie (jeśli nie wchodzisz w szczegóły) dzielą się na dwa rodzaje - przejście od ogółu do szczegółu i od szczegółu do ogółu. Pierwsza to dedukcja, druga to indukcja. Rozumowanie dedukcyjne jest tym, co zwykle nazywa się w matematyce logiczne rozumowanie, aw 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ę najprostszych poprawnych rozumowań, sylogizmy– „cegiełki” logiki, wskazując jednocześnie na typowe rozumowania, bardzo podobne do poprawnych, ale błędne (z takim „pseudologicznym” rozumowaniem często spotykamy się w mediach).

Indukcja (indukcja - po łacinie przewodnictwo) ilustruje dobrze znana legenda o tym, jak Izaak Newton sformułował prawo powszechnego ciążenia po tym, jak jabłko spadło mu na głowę. Inny przykład z fizyki: w takim zjawisku jak indukcja elektromagnetyczna pole elektryczne tworzy, „indukuje” pole magnetyczne. „Jabłko Newtona” to typowy przykład sytuacji, w której jeden lub więcej przypadków szczególnych, tj. obserwacje, „prowadzić” do ogólnego stwierdzenia, ogólny wniosek jest wyciągany 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 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ą słuszne. Rozważmy przykład ze względu na Eulera.

Obliczymy wartość trójmianu dla niektórych pierwszych wartości N:

Zauważ, że liczby otrzymane w wyniku obliczeń są liczbami pierwszymi. 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ą. Stąd hipoteza, która mogłaby tu powstać, czyli hipoteza, że dla każdego N numer
jest proste, okazuje się fałszywe.

Leibniz udowodnił to w XVII wieku dla każdej dodatniej liczby całkowitej N numer
podzielne przez 3
jest podzielna przez 5 itd. Na tej podstawie zasugerował to dla każdego nieparzystego k i dowolny naturalny N numer
podzielony przez k, ale wkrótce to zauważyłem
nie jest podzielna przez 9.

Rozważane przykłady pozwalają nam wyciągnąć ważny wniosek: stwierdzenie może być prawdziwe w wielu szczególnych przypadkach i jednocześnie ogólnie niesprawiedliwe. Kwestię ważności twierdzenia w przypadku ogólnym można rozwiązać, stosując specjalną metodę wnioskowania, tzw przez indukcję matematyczną(pełna indukcja, doskonała indukcja).

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) weryfikowana jest ważność tego oświadczeniaN=1 (podstawa indukcyjna) ,

2) zakłada się, że to stwierdzenie jest prawdziweN= k, Gdziekjest dowolną liczbą naturalną 1(założenie indukcyjne) , i biorąc pod uwagę to założenie, ustala się jego ważność dlaN= k+1.

Dowód. Załóżmy coś przeciwnego, to znaczy załóżmy, że twierdzenie to nie jest prawdziwe dla każdego naturalnego N. Wtedy jest taki naturalny M, Co:

1) zgoda na N=M niesprawiedliwe,

2) dla każdego N, mniejszy M twierdzenie jest prawdziwe (innymi słowy, M jest pierwszą liczbą naturalną, dla której twierdzenie się nie powiedzie).

To oczywiste M>1, ponieważ Dla N=1 zdanie jest prawdziwe (warunek 1). Stąd,
- Liczba naturalna. Okazuje się, że dla liczby naturalnej
stwierdzenie jest prawdziwe i dla następnej liczby naturalnej M to nie fair. Jest to sprzeczne z warunkiem 2. ■

Zauważ, że dowód wykorzystał aksjomat, ż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, że dla dowolnego naturalnego N numer
jest podzielna przez 3.

Rozwiązanie.

1) Kiedy N=1 , więc A 1 jest podzielne przez 3 i stwierdzenie jest prawdziwe dla N=1.

2) Załóż, że zdanie 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,

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

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

Rozwiązanie. Stosujemy metodę pełnej indukcji matematycznej.

1) Sprawdzamy ważność tego oświadczenia dla 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 pierwszej k+1 liczby nieparzyste są równe
, to jest .

Korzystamy z naszego założenia i otrzymujemy

. ■ 

Metoda pełnej indukcji matematycznej służy do udowodnienia niektórych nierówności. Udowodnijmy nierówność Bernoulliego.

 Przykład6.3. Udowodnij, że kiedy
i dowolny naturalny N nierówność
(nierówność Bernoulliego).

Rozwiązanie. 1) Kiedy N=1 dostajemy
, który jest poprawny.

2) Zakładamy, że o godz N=k istnieje nierówność
(*). Korzystając z tego założenia, udowodnimy to
. Zauważ, że kiedy
ta nierówność zachodzi 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 stwierdzenia, które można udowodnić za pomocą indukcji matematycznej. W takich przypadkach konieczne jest ustalenie prawidłowości i postawienie hipotezy o słuszności tej prawidłowości, a następnie przetestowanie zaproponowanej hipotezy za pomocą indukcji matematycznej.

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

Rozwiązanie. Znajdźmy sumy S 1 , S 2 , S 3 . Mamy
,
,
. Stawiamy hipotezę, że dla każdego naturalnego N formuła jest poprawna
. Aby przetestować tę hipotezę, użyjemy metody całkowitej indukcji matematycznej.

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

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

Rzeczywiście,

Zakładając więc, że hipoteza jest prawdziwa dla N=k,
, udowodniono, że jest to prawdziwe dla N=k+1 i na podstawie zasady indukcji matematycznej dochodzimy do wniosku, że wzór jest ważny dla dowolnego 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 wiadomo, że suma dwóch funkcji, które mają pewną własność S, sam ma właściwość S. Udowodnijmy, że suma dowolnej liczby funkcji ma tę własność S.

Rozwiązanie. Podstawa indukcji zawarta jest tutaj w samym sformułowaniu problemu. Przyjmując założenie indukcyjne, rozważ
Funkcje F 1 , F 2 , …, F N , F N+1, które mają właściwość S. Następnie . Po prawej stronie pierwszy wyraz ma właściwość S zgodnie z hipotezą indukcyjną drugi wyraz ma właściwość S pod warunkiem. Dlatego ich suma ma właściwość S– przez dwie kadencje podstawa indukcji „działa”.

To dowodzi twierdzenia i użyje go dalej. ■ 

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

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, użyjemy zasady niepełnej indukcji matematycznej.

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

2) Załóżmy, że to prawda dla N=k,
, czyli nierówność
. Korzystając z tego założenia, dowodzimy, że nierówność
.

T. do.
i o godz
istnieje nierówność

Na
,

wtedy to rozumiemy
. A więc prawdziwość hipotezy N=k+1 wynika z założenia, że jest ono prawdziwe dla N=k,
.

od str. 1 i 2, opierając się na zasadzie niepełnej indukcji matematycznej, wynika, że nierówność
prawdziwe dla każdego naturalnego
. ■ 

 Przykład6.7. Udowodnij, że dla dowolnej liczby naturalnej N wzór na różniczkowanie jest ważny
.

Rozwiązanie. Na N=1 ta formuła ma postać
, czyli 1=1, czyli jest to prawda. Przyjmując założenie indukcyjne, mamy:

co było do okazania ■ 

 Przykład6.8. Wykazać, że zbiór 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, a 2 1 = 2.

Zakładamy, że dowolny zbiór N elementy ma podzbiory. Jeżeli zbiór A składa się z N+1 elementy, następnie naprawiamy w nim jeden element - oznaczamy go D i podziel wszystkie podzbiory na dwie klasy - niezawierające D i zawierające D. Wszystkie podzbiory z pierwszej klasy są podzbiorami zbioru B otrzymanego z A przez usunięcie elementu D.

Zestaw B składa się z N elementów, a zatem, zgodnie z hipotezą indukcyjną, ma podzbiory, czyli w pierwszej klasie podzbiory.

Ale w drugiej klasie jest taka sama liczba podzbiorów: każdy z nich uzyskuje się z dokładnie jednego podzbioru pierwszej klasy przez dodanie elementu D. W sumie zatem zestaw A
podzbiory.

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