Udowodnij przykłady za pomocą indukcji matematycznej. Przykłady indukcji

Wstęp

Trzon

1. Indukcja całkowita i niepełna

2. Zasada indukcji matematycznej

3. Metoda indukcji matematycznej

4. Rozwiązywanie przykładów

5. Równości

6. Dzielenie liczb

7. Nierówności

Wniosek

Wykaz używanej literatury

Wstęp

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

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

Choć zakres zastosowania metody indukcji matematycznej wzrósł, w szkolnym programie nauczania poświęca się jej niewiele czasu. Cóż, powiedz mi, że te dwie lub trzy lekcje przydadzą się osobie, podczas której usłyszy pięć słów teorii, rozwiąże pięć prymitywnych problemów i w rezultacie otrzyma piątkę za to, że nic nie wie.

Ale niezwykle ważna jest umiejętność myślenia indukcyjnego.

Trzon

W swoim pierwotnym znaczeniu słowo „indukcja” odnosi się do rozumowania, w wyniku którego dochodzi się do ogólnych wniosków na podstawie szeregu konkretnych twierdzeń. Najprostszą metodą tego rodzaju rozumowania jest indukcja zupełna. Oto przykład takiego rozumowania.

Niech trzeba będzie ustalić, że każda parzysta liczba naturalna 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 liczb, którymi jesteśmy zainteresowani, jest rzeczywiście reprezentowana jako suma dwóch prostych wyrazów.

Zatem indukcja zupełna polega na samodzielnym udowodnieniu twierdzenia ogólnego w każdym ze skończonej liczby możliwych przypadków.

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

Wynik uzyskany na drodze indukcji niezupełnej pozostaje jednak jedynie hipotezą, dopóki nie zostanie udowodniony precyzyjnym rozumowaniem matematycznym, obejmującym wszystkie przypadki szczególne. Innymi słowy, niepełna indukcja w matematyce nie jest uważana za uprawnioną metodę rygorystycznego dowodu, ale jest potężną metodą odkrywania nowych prawd.

Załóżmy, że chcesz znaleźć sumę pierwszych n kolejnych liczb nieparzystych. Rozważmy szczególne przypadki:

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 danej formuły.

Indukcja całkowita ma jedynie ograniczone zastosowania w matematyce. Wiele interesujących twierdzeń matematycznych obejmuje nieskończoną liczbę przypadków specjalnych, ale nie jesteśmy w stanie przetestować ich dla 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 zastosowanie specjalnej metody rozumowania, zwanej metodą indukcji matematycznej. Jest następująco.

Załóżmy, że musisz udowodnić ważność pewnego stwierdzenia dla dowolnej liczby naturalnej n (na przykład musisz udowodnić, że suma pierwszych n liczb nieparzystych jest równa n 2). Bezpośrednia weryfikacja tego twierdzenia dla każdej wartości n jest niemożliwa, gdyż zbiór liczb naturalnych jest nieskończony. Aby udowodnić to twierdzenie, sprawdź najpierw jego ważność dla n=1. Następnie dowodzą, że dla dowolnej wartości naturalnej k z ważności rozważanego twierdzenia dla n=k wynika jego ważność dla n=k+1.

Wtedy stwierdzenie uważa się za udowodnione dla wszystkich n. W rzeczywistości stwierdzenie jest prawdziwe dla n=1. Ale wtedy jest to również prawdą dla następnej liczby n=1+1=2. Z ważności twierdzenia dla n=2 wynika jego ważność dla n=2+

1=3. Oznacza to ważność stwierdzenia dla n=4 itd. Jasne jest, że w końcu dojdziemy do dowolnej liczby naturalnej n. Oznacza to, że 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żeli propozycja A( N ), w zależności od liczby naturalnej N , prawda dla N =1 i z faktu, że jest to prawdą dla n=k (Gdzie k -dowolna liczba naturalna), wynika z tego, że jest to prawdą dla kolejnej liczby n=k+1 , to założenie A( N ) prawdziwe dla dowolnej liczby naturalnej N .

W wielu przypadkach konieczne może okazać się udowodnienie ważności danego twierdzenia nie dla wszystkich liczb naturalnych, lecz 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żeli propozycja A( N ) prawda n=p i jeśli A( k ) Þ A( k+1) dla kogokolwiek k>p, następnie zdanie A( N) prawdziwe dla każdego n>str.

Dowód metodą indukcji matematycznej przeprowadza się w następujący sposób. Najpierw sprawdza się, czy twierdzenie do udowodnienia ma n=1, tj. zostaje stwierdzona prawdziwość twierdzenia A(1). Ta część dowodu nazywana jest podstawą indukcji. Następnie następuje część dowodu zwana krokiem indukcyjnym. W tej części dowodzą słuszności twierdzenia dla n=k+1 przy założeniu ważności twierdzenia dla n=k (założenie indukcyjne), tj. udowodnić, że A(k)ÞA(k+1).

PRZYKŁAD 1

Udowodnić, ż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. Odpowiedź (1) jest prawdziwa.

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

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

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

Udowodnijmy, że wówczas twierdzenie jest prawdziwe również dla kolejnej liczby naturalnej n=k+1, czyli: Co

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

W rzeczywistości,

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

Zatem 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 poprawny; Odpowiedź (1) jest prawdziwa.

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 =(x k+1 -1)/(x-1).

Udowodnijmy, że wtedy zachodzi równość

1+x+x 2 +x 3 +…+x k +x k+1 =(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).

Zatem 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

Udowodnić, że liczba przekątnych wypukłego n-kąta jest równa n(n-3)/2.

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

A 3 ma znaczenie, bo w trójkącie

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

2A(3) jest prawdziwe.

2) Załóżmy, że w każdym przypadku

wypukły k-gon ma-

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

I k Udowodnijmy to wtedy w wypukłości

(k+1)-gon liczba

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

Niech A 1 A 2 A 3 …A k A k+1 będzie wypukłym (k+1)-kątem. Narysujmy w nim przekątną A 1 A k. Aby obliczyć całkowitą liczbę przekątnych tego (k+1)-kąta, należy policzyć liczbę przekątnych w k-kącie A 1 A 2 ...A k , do uzyskanej liczby dodać k-2, tj. należy uwzględnić liczbę przekątnych (k+1)-kątu wychodzącego z wierzchołka A k+1 oraz dodatkowo przekątną A 1 A k.

Zatem,

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

Zatem A(k)ÞA(k+1). Ze względu na zasadę indukcji matematycznej twierdzenie jest prawdziwe dla każdego wypukłego n-kąta.

PRZYKŁAD 4

Udowodnij, że dla dowolnego n prawdziwe jest następujące stwierdzenie:

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

Rozwiązanie: 1) Niech zatem n=1

X 1 =1 2 =1(1+1)(2+1)/6=1.

Oznacza to, że dla n=1 stwierdzenie jest prawdziwe.

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

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

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

X k+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, że równość jest prawdziwa dla n=k+1, zatem na mocy metody indukcji matematycznej twierdzenie jest prawdziwe dla dowolnej liczby naturalnej n.

PRZYKŁAD 5

Udowodnić, że dla dowolnej liczby naturalnej n prawdziwa jest równość:

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

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

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

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

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

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

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

Problemy z rozwiązaniami

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Skorzystajmy z metody indukcji matematycznej.

Dla n=1 stwierdzenie jest oczywiste.

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

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

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

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

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

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

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

Skorzystajmy z metody indukcji matematycznej.

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

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

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

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

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

Dowód przeprowadźmy metodą indukcji matematycznej.

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

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

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

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

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

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

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

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

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

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

To naturalne, że tak zakładamy

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

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

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

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

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

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

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

co było do okazania

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

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

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

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

Udowodnimy to twierdzenie przez indukcję.

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

więc stwierdzenie jest prawdziwe.

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

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

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

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

Odpowiedź: 2 n–2 frakcji.

Problemy bez rozwiązań

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

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

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

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

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

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

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

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

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

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

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

Metoda dowodu oparta na aksjomacie Peano 4 służy do udowadniania wielu właściwości matematycznych i różnych twierdzeń. Podstawą tego jest następujące twierdzenie.

Twierdzenie. Jeśli oświadczenie A(N) ze zmienną naturalną N prawda dla n= 1 i z faktu, że jest to prawdą dla n = k, wynika, że jest to prawdą dla następnej liczby n=k, potem stwierdzenie A(N) N.

Dowód. Oznaczmy przez M zbiór tych i tylko tych liczb naturalnych, dla których to stwierdzenie A(N) PRAWDA. Następnie z warunków twierdzenia mamy: 1) 1 M; 2) kmkM. Stąd, w oparciu o aksjomat 4, wnioskujemy, że M =N, tj. oświadczenie A(N) dotyczy każdego naturalnego N.

Metoda dowodu oparta na tym twierdzeniu nazywa się metodą indukcji matematycznej, a aksjomat jest aksjomatem indukcji. Dowód ten składa się z dwóch części:

1) udowodnić, że stwierdzenie A(N) prawda dla n= A(1);

2) przyjąć, że oświadczenie A(N) prawda dla n = k, i na podstawie tego założenia udowodnij, że stwierdzenie Jakiś) prawda dla n = k + 1, tj. że stwierdzenie jest prawdziwe A(k) A(k + 1).

Jeśli A( 1) A(k) A(k + 1) - stwierdzenie prawdziwe, następnie dochodzą do wniosku, że stwierdzenie Jakiś) prawdziwe dla dowolnej liczby naturalnej N.

Dowód metodą indukcji matematycznej można rozpocząć nie tylko od potwierdzenia prawdziwości twierdzenia n= 1, ale także z dowolnej liczby naturalnej M. W tym wypadku stwierdzenie A(N) zostanie udowodnione dla wszystkich liczb naturalnych nm.

Problem: Udowodnijmy, że dla dowolnej liczby naturalnej równość 1 + 3 + 5 … + (2 N- 1) = N.

Rozwiązanie. Równość 1 + 3 + 5 … + (2 N- 1) = N to wzór, za pomocą którego można znaleźć sumę pierwszych kolejnych nieparzystych liczb naturalnych. Na przykład 1 + 3 + 5 + 7 = 4= 16 (suma zawiera 4 wyrazy), 1 + 3 + 5 + 7 + 9 + 11 = 6= 36 (suma zawiera 6 wyrazów); jeśli suma ta zawiera 20 wyrazów wskazanego typu, to jest równa 20 = 400 itd. Po udowodnieniu prawdziwości tej równości będziemy mogli znaleźć sumę dowolnej liczby wyrazów określonego typu za pomocą wzoru.

1) Sprawdźmy prawdziwość tej równości dla n= 1. Kiedy n= 1 lewa strona równości składa się z jednego wyrazu równego 1, prawa strona równa się 1= 1. Ponieważ 1 = 1, to dla n= 1 ta równość jest prawdziwa.

2) Załóżmy, że ta równość jest prawdziwa n = k, tj. że 1 + 3 + 5 + … + (2 k- 1) = k. Na podstawie tego założenia udowadniamy, że jest to prawdą dla n = k + 1, tj. 1 + 3 + 5 + … + (2 k- 1) + (2(k + 1) - 1) = (k + 1).

Spójrzmy na lewą stronę ostatniej równości.

Z założenia suma pierwszego k warunki są równe k a zatem 1 + 3 + 5 + … + (2 k- 1) + (2(k + 1) - 1) = 1 + 3 + 5 + … + (2k- 1) + (2k+ 1)=

= k+(2k + 1) = k+ 2k + 1. Wyrażenie k+ 2k + 1 jest identycznie równa wyrażeniu ( k + 1).

Dlatego prawda tej równości dla n = k + 1 zostało udowodnione.

Zatem ta równość jest prawdziwa dla n= 1 i z jego prawdy dla n = k musi być prawdą n = k + 1.

Dowodzi to, że równość ta jest prawdziwa dla dowolnej liczby naturalnej.

Stosując metodę indukcji matematycznej można udowodnić prawdziwość nie tylko równości, ale także nierówności.

Zadanie. Udowodnij, że gdzie nN.

Rozwiązanie. Sprawdźmy prawdziwość nierówności przy n= 1. Mamy - prawdziwą nierówność.

Załóżmy, że nierówność jest prawdziwa dla n = k, te. - prawdziwa nierówność. Udowodnijmy, opierając się na założeniu, że jest to prawdą także dla n = k + 1, tj. (*).

Przekształćmy lewą stronę nierówności (*), biorąc pod uwagę, że: .

Ale , co oznacza .

Zatem ta nierówność jest prawdziwa dla n= 1, oraz z faktu, że nierówność jest prawdziwa dla niektórych n= k, odkryliśmy, że jest to również prawdą dla n= k + 1.

Zatem korzystając z aksjomatu 4 udowodniliśmy, że nierówność ta jest prawdziwa dla dowolnej liczby naturalnej.

Pozostałe twierdzenia można udowodnić metodą indukcji matematycznej.

Zadanie. Udowodnić, że dla dowolnej liczby naturalnej stwierdzenie jest prawdziwe.

Rozwiązanie. Sprawdźmy prawdziwość stwierdzenia kiedy n= 1: - stwierdzenie prawdziwe.

Załóżmy, że to stwierdzenie jest prawdziwe dla n = k: . Pokażmy za pomocą tego prawdziwość stwierdzenia kiedy n = k + 1: .

Przekształćmy wyrażenie: . Znajdźmy różnicę k I k+ 1 członków. Jeśli okaże się, że wynikowa różnica jest wielokrotnością 7 i z założenia odejmowanie jest podzielne przez 7, to odjemna jest również wielokrotnością 7:

Iloczyn jest zatem wielokrotnością 7 i .

Zatem to stwierdzenie jest prawdziwe dla n= 1 i z jego prawdy dla n = k musi być prawdą n = k + 1.

Dowodzi to, że stwierdzenie to jest prawdziwe dla dowolnej liczby naturalnej.

Zadanie. Udowodnij to dla dowolnej liczby naturalnej N 2 stwierdzenie (7-1)24 jest prawdziwe.

Rozwiązanie. 1) Sprawdźmy prawdziwość stwierdzenia kiedy N= 2: - stwierdzenie prawdziwe.

Wykład 6. Metoda indukcji matematycznej.

Nową wiedzę w nauce i życiu zdobywa się na różne sposoby, ale wszystkie (jeśli nie wdawać się 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. W matematyce powszechnie nazywa się to rozumowaniem dedukcyjnym. logiczne rozumowanie, a w naukach matematycznych dedukcja jest jedyną uprawnioną metodą dochodzenia. Zasady logicznego rozumowania zostały sformułowane dwa i pół tysiąca lat temu przez starożytnego greckiego naukowca Arystotelesa. Stworzył pełną listę najprostszych poprawnych rozumowań, sylogizmy– „cegiełki” logiki, jednocześnie wskazując typowe rozumowanie, które jest bardzo podobne do prawidłowego, ale błędne (z takim „pseudologicznym” rozumowaniem często spotykamy się w mediach).

Indukcja (indukcja - po łacinie przewodnictwo) doskonale ilustruje słynna 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 zjawisku takim 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„sugerować” stwierdzenie ogólne; na podstawie konkretnych przypadków wyciąga się ogólny wniosek. 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łędne wnioski. Hipotezy wynikające z prywatnych obserwacji nie zawsze są trafne. Rozważmy przykład ze względu na Eulera.

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

Należy pamiętać, że liczby uzyskane w wyniku obliczeń są liczbami pierwszymi. I można to bezpośrednio sprawdzić 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ł to w XVII wieku dla każdej pozytywnej całości N numer
podzielna przez 3, liczba
podzielne przez 5 itp. Na tej podstawie założył, że dla każdego nieparzystego k i wszelkie naturalne N numer
podzielone przez k, ale wkrótce to zauważyłem
nie jest podzielna przez 9.

Rozważone przykłady pozwalają na wyciągnięcie ważnego wniosku: wypowiedź może być słuszna w wielu szczególnych przypadkach i jednocześnie nieuczciwa w ogóle. Kwestię ważności twierdzenia w ogólnym przypadku można rozstrzygnąć, stosując specjalną metodę rozumowania zwaną poprzez indukcję matematyczną(indukcja całkowita, indukcja doskonała).

6.1. Zasada indukcji matematycznej.

♦ Metoda indukcji matematycznej opiera się na zasada indukcji matematycznej , czyli następująco:

1) sprawdza się ważność tego oświadczeniaN=1 (podstawa indukcyjna) ,

2) przyjmuje się za ważność tego oświadczeniaN= k, Gdziek– dowolna liczba naturalna 1(założenie indukcyjne) , i biorąc pod uwagę to założenie, ustala się jego ważnośćN= k+1.

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

1) oświadczenie dot N=M niesprawiedliwy,

2) dla wszystkich N, mniejszy M, stwierdzenie jest prawdziwe (innymi słowy, M jest pierwszą liczbą naturalną, dla której stwierdzenie nie jest prawdziwe).

To oczywiste M>1, ponieważ Dla N=1 stwierdzenie 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 niesprawiedliwe. Jest to sprzeczne z warunkiem 2. ■

Należy zauważyć, że w dowodzie wykorzystano aksjomat, że każdy zbiór liczb naturalnych zawiera najmniejszą liczbę.

Dowód oparty na zasadzie indukcji matematycznej nazywa się metodą całkowitej indukcji matematycznej .

 Przykład6.1. Udowodnij to dla dowolnego naturalnego N numer
podzielna przez 3.

Rozwiązanie.

1) Kiedy N=1, więc A 1 jest podzielna przez 3, a stwierdzenie jest prawdziwe, gdy N=1.

2) Załóżmy, że stwierdzenie jest prawdziwe dla N=k,
, czyli ta liczba
jest podzielna przez 3 i ustalamy to kiedy N=k Liczba +1 jest podzielna przez 3.

W rzeczywistości,

Ponieważ Każdy wyraz jest podzielny przez 3, wówczas ich suma jest również podzielna przez 3. ■ 

 Przykład6.2. Udowodnić, że suma pierwszego N naturalne liczby nieparzyste są równe kwadratowi ich liczby, to znaczy.

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

1) Sprawdzamy ważność tego stwierdzenia, kiedy N=1: 1=1 2 – to prawda.

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

Korzystamy z naszego założenia i otrzymujemy

. ■ 

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

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

Rozwiązanie. 1) Kiedy N=1 otrzymujemy
, co jest prawdą.

2) Zakładamy, że kiedy N=k istnieje nierówność
(*). Korzystając z tego założenia, udowodnimy to
. Zwróć uwagę, kiedy
nierówność ta jest spełniona i dlatego wystarczy rozważyć ten przypadek
.

Pomnóżmy obie strony nierówności (*) przez liczbę
i otrzymujemy:

To znaczy (1+
.■ 

Dowód metodą niepełna indukcja matematyczna jakieś stwierdzenie w zależności od N, Gdzie
przeprowadza się w podobny sposób, tyle że na początku uczciwość ustala się dla najmniejszej wartości N.

Niektóre problemy nie zawierają wyraźnie stwierdzenia, które można udowodnić za pomocą indukcji matematycznej. W takich przypadkach należy samodzielnie ustalić wzór i postawić hipotezę o słuszności tego wzorca, a następnie skorzystać z metody indukcji matematycznej, aby przetestować zaproponowaną hipotezę.

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

Rozwiązanie. Znajdźmy sumy S 1 , S 2 , S 3. Mamy
,
,
. Zakładamy, że dotyczy to każdego naturalnego N formuła jest aktualna
. Aby przetestować tę hipotezę, zastosujemy metodę całkowitej indukcji matematycznej.

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

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

W rzeczywistości,

Opierając się więc na założeniu, że hipoteza jest prawdziwa, gdy N=k,
, udowodniono, że jest to prawdą także dla N=k+1 i na podstawie zasady indukcji matematycznej stwierdzamy, że wzór jest ważny dla dowolnej liczby naturalnej 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 musisz udowodnić, że suma dowolnej liczby
funkcji jednostajnie ciągłych jest funkcją jednostajnie ciągłą. Ponieważ jednak nie wprowadziliśmy jeszcze pojęcia „funkcji jednostajnie ciągłej”, postawmy problem bardziej abstrakcyjnie: niech będzie wiadomo, że suma dwóch funkcji mających jakąś własność S, sam ma tę właściwość S. Udowodnimy, że suma dowolnej liczby funkcji ma tę własność S.

Rozwiązanie. Podstawą indukcji jest tutaj sformułowanie samego problemu. Po przyjęciu założenia indukcyjnego rozważmy
funkcje F 1 , F 2 , …, F N , F N+1, które mają tę właściwość S. Następnie . Po prawej stronie pierwszy termin ma właściwość S zgodnie z hipotezą indukcyjną drugi człon ma tę właściwość S według stanu. W związku z tym ich suma ma własność S– dla dwóch kadencji baza indukcji „działa”.

To potwierdza stwierdzenie i będziemy z niego dalej korzystać. ■ 

 Przykład6.6. Znajdź wszystko naturalne N, dla którego nierówność jest prawdziwa

Rozwiązanie. Rozważmy 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. Możemy zatem postawić hipotezę: nierówność
ma miejsce dla każdego
. Aby udowodnić prawdziwość tej hipotezy, skorzystamy z zasady niepełnej indukcji matematycznej.

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

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

Ponieważ
i o godz
istnieje nierówność

Na
,

wtedy to zrozumiemy
. Zatem prawdziwość hipotezy przy N=k+1 wynika z założenia, że prawdą jest, gdy N=k,
.

Z akapitów. 1 i 2, bazując na zasadzie niepełnej indukcji matematycznej, wynika z nierówności
dotyczy każdego naturalnego
. ■ 

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

Rozwiązanie. Na N=1 wygląda ta formuła
lub 1=1, czyli jest poprawne. Przyjmując założenie indukcyjne, mamy:

co było do okazania ■ 

 Przykład6.8. Udowodnić, że zbiór składający się z N elementy, ma podzbiory

Rozwiązanie. Zestaw składający się z jednego elementu A, ma dwa podzbiory. Jest to prawdą, ponieważ wszystkie jego podzbiory są zbiorem pustym i samym zbiorem pustym oraz 2 1 =2.

Załóżmy, że każdy zbiór N elementy ma podzbiory Jeżeli zbiór A składa się z N+1 elementy, następnie ustalamy w nim jeden element - oznaczamy go D, i podzielić wszystkie podzbiory na dwie klasy – te, które nie zawierają D i zawierający D. Wszystkie podzbiory pierwszej klasy są podzbiorami zbioru B otrzymanego z A poprzez usunięcie elementu D.

Zestaw B składa się z N elementy, a zatem, przez indukcję, ma podzbiorów, a więc w pierwszej klasie podzbiory

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

W ten sposób stwierdzenie zostało udowodnione. Zauważ, że dotyczy to również zbioru składającego się z 0 elementów – zbioru pustego: ma on pojedynczy podzbiór – sam siebie oraz 2 0 = 1. ■ 

Metoda indukcji matematycznej

Wstęp

Trzon

Indukcja całkowita i niepełna
Zasada indukcji matematycznej
Metoda indukcji matematycznej
Rozwiązywanie przykładów
Równości
Dzielenie liczb
Nierówności

Wniosek

Wykaz używanej literatury

Wstęp

Ale niezwykle ważna jest umiejętność myślenia indukcyjnego.

Trzon

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 liczb, którymi jesteśmy zainteresowani, jest rzeczywiście reprezentowana jako suma dwóch prostych wyrazów.

Zatem indukcja zupełna polega na samodzielnym udowodnieniu twierdzenia ogólnego w każdym ze skończonej liczby możliwych przypadków.

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

Załóżmy, że chcesz znaleźć sumę pierwszych n kolejnych liczb nieparzystych. Rozważmy szczególne przypadki:

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 danej formuły.

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

1=3. Oznacza to ważność stwierdzenia dla n=4 itd. Jasne jest, że w końcu dojdziemy do dowolnej liczby naturalnej n. Oznacza to, że 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żeli zdanie A(n) w zależności od liczby naturalnej n jest prawdziwe dla n=1 oraz z tego, że jest prawdziwe dla n=k (gdzie k jest dowolną liczbą naturalną), wynika, że jest to prawdziwe także dla następna liczba n=k +1, to założenie A(n) jest prawdziwe dla dowolnej liczby naturalnej n.

Jeśli zdanie A(n) jest prawdziwe dla n=p i jeśli A(k)ÞA(k+1) dla dowolnego k>p, to zdanie A(n) jest prawdziwe dla dowolnego n>p.

Udowodnić, ż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. Odpowiedź (1) jest prawdziwa.

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

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

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

Udowodnijmy, że wówczas twierdzenie jest prawdziwe również dla kolejnej liczby naturalnej n=k+1, czyli: Co

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

W rzeczywistości,

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

Zatem 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.

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 poprawny; Odpowiedź (1) jest prawdziwa.

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 =(x k+1 -1)/(x-1).

Udowodnijmy, że wtedy zachodzi równość

1+x+x 2 +x 3 +…+x k +x k+1 =(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).

Zatem 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.

Udowodnić, że liczba przekątnych wypukłego n-kąta jest równa n(n-3)/2.

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

A 3 ma znaczenie, bo w trójkącie

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

2A(3) jest prawdziwe.

2) Załóżmy, że w każdym przypadku

wypukły k-gon ma-

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

I k Udowodnijmy to wtedy w wypukłości

(k+1)-gon liczba

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

Zatem,

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

Zatem A(k)ÞA(k+1). Ze względu na zasadę indukcji matematycznej twierdzenie jest prawdziwe dla każdego wypukłego n-kąta.

Udowodnij, że dla dowolnego n prawdziwe jest następujące stwierdzenie:

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

Rozwiązanie: 1) Niech zatem n=1

X 1 =1 2 =1(1+1)(2+1)/6=1.

Oznacza to, że dla n=1 stwierdzenie jest prawdziwe.

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

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

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

X k+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, że równość jest prawdziwa dla n=k+1, zatem na mocy metody indukcji matematycznej twierdzenie jest prawdziwe dla dowolnej liczby naturalnej n.

Udowodnić, że dla dowolnej liczby naturalnej n prawdziwa jest równość:

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 = k 2 (k+1) 2 /4.

3) Udowodnimy prawdziwość tego twierdzenia 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 widać, że twierdzenie jest prawdziwe dla n=k+1, zatem równość jest prawdziwa dla dowolnej liczby naturalnej n.

Udowodnij to

((2 3 +1)/(2 3 -1))'((3 3 +1)/(3 3 -1))'…'((n 3 +1)/(n 3 -1))= 3n(n+1)/2(n 2 +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. to prawda.

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) Udowodnijmy poprawność wyrażenia na 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, że równość jest prawdziwa dla n=k+1, zatem na mocy metody indukcji matematycznej twierdzenie jest prawdziwe dla dowolnego n>2

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) Udowodnimy prawdziwość tego twierdzenia 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 także słuszność równości dla n=k+1, zatem twierdzenie jest prawdziwe dla dowolnej liczby naturalnej n.

Udowodnij, że tożsamość jest poprawna

(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 jasno wynika, że twierdzenie jest prawdziwe dla dowolnej liczby naturalnej n.

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

Rozwiązanie: 1) Niech zatem n=1

11 3 +12 3 =(11+12)(11 2 -132+12 2)=23'133.

Ale (23'133) jest podzielne przez 133 bez reszty, co oznacza, że dla n=1 stwierdzenie jest prawdziwe; Odpowiedź (1) jest prawdziwa.

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) jest podzielne 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(11 k+2 +12 2k+1)+133'12 2k+1 .

Otrzymaną sumę dzielimy przez 133 bez reszty, gdyż jej pierwszy wyraz jest z założenia podzielny przez 133 bez reszty, a w drugim z czynników wynosi 133. Zatem A(k)ÞA(k+1). Twierdzenie zostało udowodnione metodą indukcji matematycznej.

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

Rozwiązanie: 1) Niech n=1, to X 1 =7 1 -1=6 dzielimy przez 6 bez reszty. Oznacza to, że gdy n=1 stwierdzenie jest prawdziwe.

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

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

3) Udowodnijmy, że twierdzenie 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 dzieli się przez 6 z założenia, a drugi wyraz to 6. Oznacza to, że 7 n -1 jest wielokrotnością 6 dla dowolnego naturalnego n. Twierdzenie zostało udowodnione metodą indukcji matematycznej.

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

X 1 =3 3-1 +2 4-3 =3 2 +2 1 =11 dzieli się przez 11 bez reszty. Oznacza to, że dla n=1 stwierdzenie jest prawdziwe.

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

X k =3 3k-1 +2 4k-3 dzieli się przez 11 bez reszty.

3) Udowodnijmy, że twierdzenie 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 3k-1 +2 4k-3 jest podzielny przez 11 z założenia, drugi jest podzielny przez 11, ponieważ jednym z jego czynników jest liczba 11. Oznacza to, że suma jest podzielna przez 11 bez reszty dla dowolnej liczby naturalnej n. Twierdzenie zostało udowodnione metodą indukcji matematycznej.

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

Rozwiązanie: 1) Niech n=1, wtedy 11 2 -1=120 jest podzielne przez 6 bez reszty. Oznacza to, że gdy n=1 stwierdzenie jest prawdziwe.

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

11 2k -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, liczbę 120, a drugi jest podzielny przez 6 bez reszty z założenia. Oznacza to, że suma jest podzielna przez 6 bez reszty. Twierdzenie zostało udowodnione metodą indukcji matematycznej.

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

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

Kiedy n=0

3 3 -1=26 dzieli się przez 26

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

3 3k+3 -1 jest podzielne przez 26

Udowodnijmy, że to stwierdzenie

prawdziwe dla n=k+1.

3 3k+6 -1=27'3 3k+3 -1=26'3 3л+3 +(3 3k+3 -1) – podzielone przez 26

Teraz przeprowadzimy dowód twierdzenia sformułowanego w stwierdzeniu problemu.

1) Oczywiście, gdy n=1, stwierdzenie jest prawdziwe

3 3+3 -26-27=676

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

wyrażenie 3 3k+3 -26k-27 dzieli się przez 26 2 bez reszty.

3) Udowodnijmy, że twierdzenie 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; pierwsza jest podzielna przez 26 2, ponieważ udowodniliśmy podzielność wyrażenia w nawiasach przez 26, a druga jest podzielna przez hipotezę indukcyjną. Twierdzenie zostało udowodnione metodą indukcji matematycznej.

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

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

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

(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, czyli że nierówność

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

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

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

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

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

Rozważmy prawą stronę ostatniej nierówności

stva; mamy

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

W rezultacie to otrzymujemy

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

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

Udowodnić, ż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) Gdy m=1

(1+a+a 2) 1 > 1+a+(2/2)'a 2 Obie strony 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ść obowiązuje dla dowolnego m naturalnego.

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

3 n >n´2 n+1 .

Rozwiązanie: Zapiszmy nierówność w postaci

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 słuszność nierówności dla n=k+1.

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

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

Na mocy metody indukcji matematycznej nierówność dotyczy dowolnej liczby naturalnej n.

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

1+(1/2 2)+(1/3 2)+…+(1/n 2)<1,7-(1/n).

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

1+(1/2 2)+(1/3 2)=245/180<246/180=1,7-(1/3).

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

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

3) Udowodnijmy zasadność nie-

równość dla n=k+1

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

Udowodnimy, że 1,7-(1/k)+(1/(k+1) 2)<1,7-(1/k+1)Û

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

Ûk(k+2)<(k+1) 2Û k 2 +2k

To drugie jest oczywiste i dlatego

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

Nierówność zostaje udowodniona metodą indukcji matematycznej.

Wniosek

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

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

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

MATEMATYKA:

WYKŁADY, PROBLEMY, ROZWIĄZANIA

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

ALGEBRA I POCZĄTKI ANALIZY

Podręcznik / I.T. Demidov, A.N. Kołmogorow, SI Shvartsburg, OS Ivashev-Musatov, BE Weitz. „Oświecenie” 1975.

Problemy z rozwiązaniami

Problemy bez rozwiązań

Może Cię zainteresuje