Indukcja mat fol, szkoła, Matematyka Dyskretna, Wykłady
[ Pobierz całość w formacie PDF ]
//-->Indukcja matematycznaDowodzimy e własnośćT(n)zachodzi dla ka dego naturalnegon≥n.Kroki indukcji:1. Sprawdzić eT(n)2. Wykazać eT(n)⇒T(n+1)dla ka dego naturalnegon≥n.PrzykładyPrzykład1.Sprawdzić prawdziwość wzoru:Sn= 1 + 2 + 3 + ... +n=n(n+1)/2OznaczamyL(n)= 1 + 2 + 3 + ... +n1. Sprawdzamy dlan= 0.L(0) =0P(0)= 0L=PP(n)=n(n+1)/22. Nale y wykazaćT(n)⇒T(n+1)czyli[L(n) =P(n)]⇒[L(n+1) =P(n+1)]L(n+1)= 1 + 2 + 3 + ... +n+(n+1)2=L(n)+ (n+1) ={ korzystamy z zało enie indukcyjnegoL(n)=P(n)}=P(n) +(n+1) =n(n+1)/2+(n+1) = (n+1)/2⋅(n+2) = (n+1)(n+2)/2=P(n+1).Zatem wzórSn= 1 + 2 + 3 + ... +n=n(n+1)/2jest słuszny dlaka degon≥0 .Przykład2.Sprawdzić prawdziwość wzoru:Sn= 12+ 22+ 32+ ... +n2=n(n+1)(2n+1)/6n≥0.OznaczamyL(n)= 12+ 22+ 32+ ... +n2P(n)=n(n+1)(2n+1)/61.L(0)= 0 =P(0)2. [L(n) =P(n)]⇒[L(n+1) =P(n+1)]L(n+1)= 12+ 22+ 32+ ... +n2+(n+1)2=L(n)+ (n+1)2=P(n)+(n+1)2=n(n+1)(2n+1)/6+ (n+1)2= (1/6)*(n+1) [n(2n+1) + 6(n+1)]={przekształcamy [ ]:n(2n+1)+ 6(n+1) = (n+2)(2n+3) }= (1/6)*(n+1)(n+2)(2n+3) = (1/6)*(n+1)(n+2)(2(n+1)+1) =P(n+1)Własność została wykazana dla ka degon≥0 .MD - Indukcja1Przykład3.Wykazać, e liczba postaciq(n)= 5n– 4n –1 dla ka dego naturalnegon≥1 jest podzielna przez 16.zapiszemy krócej: 16 |q(n)= 5n– 4n –1n∈N,n≥11.n=1. q(1)= 51– 4⋅1–1 = 0 16 |q(1)2. 16 |q(n)⇒16 |q(n+1)q(n+1)= 5n+1– 4(n+1)–1 = 5⋅5n– 4n – 4–1 = 5⋅5n– 4n – 5== 5⋅5n– 20n +16n – 5 = 5 (5n– 4n –1) +16n= 5q(n) +16nPierwszy składnik wyra eniaq(n+1)jest podzielny przez 16 namocy zało enia indukcyjnego, drugi jest wielokrotnością 16 – stądq(n+1)podzielne przez 16.Zatem liczba postaciq(n)= 5n– 4n –1 dla ka dego naturalnegon≥1 jest podzielna przez 16.Przykład4.Wykazać, e dlan≥10prawdziwa jest nierównośćn3< 2n.Ozn:L(n)=n3P(n)= 2nL(n)<P(n)n≥101.n= 10 103= 1000 < 210= 1024 nierówność prawdziwa.2.L(n)<P(n)⇒L(n+1)<P(n+1) n≥10L(n+1)= (n+1)3=n3+ 3n2+ 3n + 1ale dlan>10 jest 3n2+ 3n +1 < 3n2+3n2+3n2< 10n2<n3,więcL(n+1)= (n+1)3< 2n3< 2⋅2n= 2n+1=P(n+1)Kroki indukcyjne 1 i 2 zostały wykonane, a więc dlan≥10prawdziwajest nierównośćn3< 2n.MD - Indukcja2
[ Pobierz całość w formacie PDF ]