indukcja matematyczna.pdf

Indukcjamatematyczna

Dowodyindukcyjneprzeprowadzasi¦wedługjednegoschematu-prawidłowo

skonstruowanydowóduwzgl¦dniaWSZYSTKIEkrokitegoschematu.Otoko-

lejnepunkty:

1.Sprawdzamy,czytwierdzeniezachodzidladowolnejustalonejliczbynatu-

ralnej.Wtymceluwybieramydowoln¡liczb¦spełniaj¡c¡zało»eniatwier-

dzenia(toznaczy,je±liwtwierdzeniumamy,»ezachodzionodlawszyst-

kichliczbnaturalnychwi¦kszychlubrównych5toniemo»emywybra¢3

tylkoconajmniej5).Naogółwybieramy1lub2.

2.Drugipunkttotakzwanezało»enieindukcyjne.Piszemy: n = k iprzepi-

sujemytre±¢twierdzenia,zast¦puj¡cznaczki n znaczkami k .

3.Trzecipunkttotezaindukcyjna.Piszemy: n = k +1iprzepisujemytre±¢

twierdzeniazast¦puj¡cznaczki n znaczkami( k +1)–uwaga!wpisa¢w

nawiasie!!!

4.Czwartypunkttowła±ciwydowód.Całatrudno±¢poleganatym,»eby

takprzekształci¢tez¦indukcyjn¡,»eby„wył¡czy¢”zniejzało»enieinduk-

cyjneipewn¡„reszt¦”.Dlazało»eniaindukcyjnegotwierdzeniezachodzi.

Pozostajeudowodni¢,»ezachodzidlawył¡czonej„reszty”.Naogółjestto

łatwozauwa»y¢.

Przykład1.(Typ1:udowodni¢podzielno±¢liczby) Wykaza¢,»e3 | 4 n +2

(czytamy:trzyjestdzielnikiemczterydon-tejplus2).

1.Sprawdzamydla n =2(mo»nawybra¢dowoln¡rozs¡dn¡liczb¦natural-

n¡).Obliczamy4 n +2=4 2 +2=18,ajakwiadomo,18jestpodzielne

przez3.Jaknarazie,twierdzeniezachodzi.Niewiadomo,czyzachodzidla

WSZYSTKICHliczbnaturalnych.

2.Piszemy:„Zało»enieindukcyjne: n = k ”iprzepisujemytre±¢twierdzenia,

zmieniaj¡c n na k :3 | 4 k +2.

3.Piszemy:„Tezaindukcyjna: n =( k +1)”iprzepisujemytre±¢twierdzenia,

zmieniaj¡c n na( k +1):3 | 4 ( k +1) +2.

4.Piszemy:„Dowód:”iprzekształcamywzór4 k +1 +2wtakisposób,»eby

wył¡czy¢zniego4 k +2.Zauwa»my,»e4 ( k +1) +2mo»nazapisa¢jako

4 · 4 k +2,atozkoleijako3 · 4 k +4 k +2.Drugacz¦±¢wzoru(poznaku+)

tozało»enieindukcyjne,azatemjestpodzielneprzez3.Pierwszacz¦±¢,

to3 · 4 k .Aleiloczynliczby3ijakiejkolwiekinnejliczbyjestpodzielny

przez3.Sumaliczbpodzielnychprzez3te»jestpodzielnaprzez3.Dowód

zako«czony(zwyklezapisujemyzprawejstronysymbol ).

Przykład2.(Typ2:Wzorynasumy n wyrazówci¡gu)

Udowodni¢,»e1+3+ ··· +(2 n − 1)= n 2 .

UWAGA!Wtymtypiedowodów n oraz k oznaczaj¡numer,alete»ILO

kolejnychwyrazówci¡gu.

1.Sprawdzamynp.dla n =4.Wtwierdzeniach,»ejaki±wzórjestrówny

innemu,mo»emymówi¢oLEWEJiPRAWEJstronierównania.St¡d

piszemy:

L =1+3+5+7=16,(bierzemy4pierwszewyrazyci¡gupolewej

stronie).

P =4 2 =16

L = P –dlawybranejliczbywzórzachodzi.

2.Zało»enieind.: n = k

Przepisujemytwierdzenie,zast¦puj¡cliterk¦ n literk¡ k :

1+3+5+ ··· +(2 k − 1)= k 2

3.Tezaind.: n =( k +1).Przepisujemytwierdzeniewtensposób,»elew¡stro-

n¦przepisujemyzzało»eniaindukcyjnegoiDOPISUJEMY k + pierwszy

wyraz,zast¦puj¡cliterk¦ n wewzorzesymbolem( k +1)

1 +3+5+ ·· · +(2 k − 1 )

| {z }

przepisane

+( 2( k + 1 ) − 1 )

| {z }

dopisane

=( k +1) 2 .

4.Dowód:

Obliczamylew¡stron¦:

L =1 +3+5+ ·· · +(2 k − 1 )

| {z }

lewastronazało»enia

+(2( k +1) − 1)

= k 2

|{z}

prawastronazało»enia

+(2( k +1) − 1)

= k 2 +2 k +1

P =( k +1) 2 = k 2 +2 k +1

L = P

c PiotrSojka(ps@math.us.edu.pl),Ostatniaaktualizacja:8listopada2006

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: