Jak rozwiazac zadania na indukcje matematyczna?
Hubert Karbowy
Czy ktos z was moglby mi wytlumaczyc na przykladach na czym dokladnie
polega zasada indukcji matematycznej? I jeszcze jak rozwiazac takie
zadania:
1. Wykaz, ze dla kazdej liczby naturalnej dodatniej prawdziwe sa
nierownosci:
a) 2 + 3^n > 2^n + 1
b) 1 + 1/(2^2) + 1/(3^2) + ... + 1/(n^2) =< 2 - 1/n
c) 1/(n+1) + 1/(n+2) + 1/(n+3) + ... + 1/(3n+1) > 1
2. Dla jakich naturalnych n prawdziwe sa podane nierownosci? Sformuluj
hipoteze i udowodnij ja stosujac zasade indukcji:
a) 2^n > 2n
b) 2^n > 2n + 1
c) 2^n > n^2
d) 2^n > n^3
e) (1-1/4) * (1-1/9) * (1-1/16) * ... * [1-1/(n^2)] = (n+1)/(2n)
f) 2^n > 5n
Mam nadzieje, ze rozczytacie sie z tych ulamkow ;) Te dwa zadania
pochodza ze "Zbioru zadan z matematyki dla klasy I i II liceum
ogolnoksztalcacego" - autorzy: Norbert Drobka i Karol Szymanski,
zadania nr 11.3 i 11.4 str. 147.
Zaraz po wakacjach praca klasowa z ciagow, a ja nic nie rozumiem.
Dzieki za pomoc!
Hubert Karbowy
h...@bbs.chip.pl
Piotr
prawdziwe dla pierwszego wyrazu z ciago oraz dla wyrazu n i n+1
w Twoich zadaniach (zakladajac ze n to liczba naturalna) nalezy
sprawdzic prawdziwosc dla n=0/n=1 oraz na liczbach ogolnych
dla n i n+1
Piotr
Matrix
Don't worry - be happy
btw. w ciagach nie ma za wiele do rozumienia
---------------
[ M ][ A ][ T ][ R ][ I ][ X ] (mailto: tkm...@box43.gnet.pl)
*Rob i przerabiaj - dzien jest dostatecznie dlugi*
Marek Szyjewski
>This is a multi-part message in MIME format.
>--------------F7D8B0F2260D0FBC4BE64BD4
>Content-Type: text/plain; charset=us-ascii
>Content-Transfer-Encoding: 7bit
>
>indukcja matematyczna mowi ze zdanie jest prawdziwe jesli jest
>prawdziwe dla pierwszego wyrazu z ciago oraz dla wyrazu n i n+1
To jest nonsens, a nie zasada indukcji. Zasada indukcji wyglada tak:
F(1) ==> (((F(k) ==> F(k+1)) ==> dla kazdego n F(n))
Zeby za jej pomoca udowodnic twierdzenie postaci "dla kazdego n F(n)"
wystarczy udowodnic dwa fakty:
1. prawdziwe jest zdanie F(1)
2. dla dowolnej liczby naturalnej k przwdziwa jest implikacja
F(k) ==> F(k+1).
Jesli celem jest udowodnienie zdania "F(n) dla dowolnego n" i udalo
sie udowodnic zdania: F(n) i jeszcze cos (np. F(n+1)), to nie ma co
dalej robic, ani stosowac zasad - F(n) jest udowodnione.
>w Twoich zadaniach (zakladajac ze n to liczba naturalna) nalezy
>sprawdzic prawdziwosc dla n=0/n=1 oraz na liczbach ogolnych
>dla n i n+1
Nie. Chodzi o udowodnienie (jak w tresci zadan) prawdziwosci tych zdan
dla dowolnego n (czyli n bedacego zmienna, przebiegajaca liczby
naturalne).
>>
>> 1. Wykaz, ze dla kazdej liczby naturalnej dodatniej prawdziwe sa
>> nierownosci:
>>
>> a) 2 + 3^n > 2^n + 1
>>
Wygodniej dowodzic rownowaznej nierownosci 3^n > 2^n -1
Oznaczenia: F(n) = "3^n > 2^n -1"
1. Zdanie F(1) wyglada tak: 3^1 > 2^1 - 1 i jest prawdziwe (bo jest
nierownoscia 3>1)
2. Dla dowolnej liczby naturalnej k (dla zmiennej k) dowodzimy
implikacji F(k) ==> F(k+1). Jak zwykle przy dowodzeniu implikacji
wystarczy zalozyc, ze poprzednik implikacji (tu - F(k) jest prawdziwy.
Zakladamy wiec (to sie nazywa zalozenie indukcyjne), ze
3^k > 2^k - 1
i dowodzimy zdania F(k+1), czyli zdania 3^(k+1)> 2^(k+1) - 1.
3^(k+1) = 3*3^k > 3*(2^k - 1) = 3*2^k - 3 = (2+1)*2^k - 3
= 2*2^k + 2^k -3 = 2^(k+1) + (2^k -3) >= 2^(k+1) + (2-3) =
= 2^(k+1) -1
3^(k+1) > 2^(k+1) -1
Ostatecznie: ilekroc F(k) jest prawda, to jest rowniez prawda F(k+1),
czyli prawdziwa jest implikacja F(k) ==> F(k+1).
Teraz nastepuje "staly element gry", z reguly pomijany:
prawdziwe sa trzy zdania:
1) F(1) ==> ((F(k) ==> F(k+1)) ==> dla kazdego n F(n)) (bo to jest
aksjomat, zwany zasada indukcji)
2) F(1) (sprawdzone w 1.)
3) F(k) ==> F(k+1) (sprawdzone w 2.)
z prawdziwosci 1) i 2) wynika prawdziwosc zdania
4) ((F(k) ==> F(k+1)) ==> dla kazdego n F(n))
(uczenie: zastosowano regule odrywania do przslanek 1) i 2))
a z prawdziwosci 4) i 3) wynika prawdziwosc zdania
5) dla kazdego n F(n)
ktore wlasnie nalezalo udowodnic.
>> b) 1 + 1/(2^2) + 1/(3^2) + ... + 1/(n^2) =< 2 - 1/n
Teraz juz bez "stalych fragmentow gry":
F(n) = "1 + 1/(2^2) + 1/(3^2) + ... + 1/(n^2) =< 2 - 1/n"
W szczegolnosci F(1) ma po lewej stronie n=1 skladnik, czyli 1.
F(k) = "1 + 1/(2^2) + 1/(3^2) + ... + 1/(k^2) =< 2 - 1/k" ma po
prawej stronie k skladnikow,
F(k+1) = "1 + 1/(2^2) + 1/(3^2) + ... + 1/((k+1)^2) =< 2 - 1/(k+1)"
ma po lewej stronie k+1 skladnikow, itd.
Dowod indukcyjny:
1. F(1) = "1 =< 2-1" jest, jak latwo sprawdzic, zdaniem prawdziwym.
2. Zakladamy, ze F(k) jest prawda, czyli ze
1 + 1/(2^2) + 1/(3^2) + ... + 1/(k^2) =< 2 - 1/k.
Sprawdzamy F(k+1):
1 + 1/(2^2) + 1/(3^2) + ... + 1/((k+1)^2) =
1 + 1/(2^2) + 1/(3^2) + ... + 1/(k^2) + 1/((k+1)^2) =<
2 - 1/k + 1/((k+1)^2 = 2 - (1/(k+1))[(k+1)/k - 1/(k+1)] =
2 - (1/(k+1))[(1+ 1/k - 1/(k+1)] = 2 - (1/(k+1))[(1+ 1/k(k+1)] <
2 - (1/(k+1))*1 = 2 - 1/(k+1)
i F(k+1) okazuje sie prawdziwe przy zalozeniu F(k).
"Stale elementy gry" i nierownosc udowodniona dla kazdego n
naturalnego.
>>
>> c) 1/(n+1) + 1/(n+2) + 1/(n+3) + ... + 1/(3n+1) > 1
F(n) = "1/(n+1) + 1/(n+2) + 1/(n+3) + ... + 1/(3n+1) > 1", wiadomo,
jak utworzyc F(1), F(k) i F(k+1) - lewa strona F(n) ma 2n+1
skladnikow, lewa strona F(1) ma 2*1+1 = 3 skladniki, itd.
1. F(1) = "1/2 + 1/3 + 1/4 > 1" jest zdaniem prawdziwym, bo jest
rownowazne zdaniu 13/12 > 1.
2. Zakladamy, ze zdanie F(k) jest prawdziwe:
1/(k+1) + 1/(k+2) + 1/(k+3) + ... + 1/(3k+1) > 1.
Sprawdzamy prawdziwosc F(k+1):
1/((k+1)+1) + 1/((k+1)+2) + 1/((k+1)+3) + ... + 1/(3(k+1)+1) =
1/(k+2) + 1/(k+3) + 1/(k+4) + ... + 1/(3k +1) + 1/(3k+2) + 1/(3k+3) +
1/(3k+4) =
[1/(k+1) + 1/(k+2) + 1/(k+3) + ... + 1/(3k+1)] - 1/(k+1) + 1/(3k+2) +
1/(3k+3) + 1/(3k+4) > 1- 1/(k+1) + 1/(3k+2) + 1/(3k+3) + 1/(3k+4) =
(ulamki do wspolnego mianownika)
1 - (3k+2)(3k+3)(3k+4)/(k (3k+2)(3k+3)(3k+4)) + ... =
1 + 2/(3( k+1)( 3k+2)( 3k+4)) >1
i "stale elementy gry".
I tak dalej.
Z powazaniem
Marek Szyjewski
My, samotnicy, powinnismy trzymac sie razem!
Dawid Toton
>>prawdziwe dla pierwszego wyrazu z ciago oraz dla wyrazu n i n+1
>
>To jest nonsens, a nie zasada indukcji. Zasada indukcji wyglada tak:
>
>F(1) ==> (((F(k) ==> F(k+1)) ==> dla kazdego n F(n))
>
( F(1) ^ ( dla każdego n (F(n)==>F(n+1)) ) ) ==> dla każdego n
F(n) )
jest poprawne?
[d]
----------------------
Marek Szyjewski
Jest poprawne.
1. Forma zdaniowa zawierajaca jedna zmienna wolna - np. napis:
F(k) ==> F(k+1)
ze zmienna wolna k jest prawdziwa (ma dowod) wtedy i tylko wtedy, gdy
prawdziwe jest (ma dowod) zdanie
dla kazdego k F(k) ==> F(k+1).
Dowod takiego zdania zaczyna sie od opuszczenia duzego kwantyfikatora,
nieprawdaz? Korzysc dydaktyczna: nie trzeba tlumaczyc opuszczania
kwantyfikatora.
2. Zdania "dla kazdego x F(x)" i "dla kazdego y F(y)" sa rownowazne.
Jest obojetne, jaki symbol oznacza zmienna zwiazana przez
kwantyfikator. Uzylem k zamiast n z przyczyn dydaktycznych (aby
udaremnic "dowody" na skroty: zalozenie indukcyjne: F(n), wiec F(n) z
tezy jest prawdziwe).
3. Zdania (p i q) ==> r oraz p ==> (q==>r) sa rownowazne - jest to
tresc praw importacji i eksportacji. Aby wiedzac, ze takie zdanie jest
prawdziwe, udowodnic r, trzeba
- w formie koniunkcyjnej: udowodnic p i udowodnic q;
- w formie implikacyjnej: udowodnic p i udowodnic q.
Forma z koniunkcja wymaga znajomosci metody dowodzenia koniunkcji i
reguly odrywania, forma czysto implikacyjna - tylko reguly odrywania.
Ma wiec rowniez zalety dydaktyczne - dziala na uczniow, ktorym stale
myli sie koniunkcja z alternatywa i akcentuje dedukcyjna strukture.