Indukcja matematyczna

Indukcja matematyczna

Indukcja matematyczna, zwana też indukcją zupełną, jest to metoda dowodzenia twierdzeń o liczbach naturalnych.

Niech T(n) oznacza formę zdaniową zmiennej n określoną w dziedzinie . Jeśli w miejsce n podstawimy dowolną liczbę naturalną, to T(n) stanie się zdaniem prawdziwym albo fałszywym, zależnie od wartości n. Jeżeli, na przykład, T(n) oznacza wypowiedź "n jest podzielne przez 3", to T(6) jest zdaniem prawdziwym, natomiast T(7) jest zdaniem fałszywym. Jeżeli T(n) oznacza nierówność n < n2, to T(n) jest zdaniem prawdziwym dla każdej liczby naturalnej większej od 1, natomiast zdanie T(1) jest fałszywe.

Metoda indukcji matematycznej opiera się na następującej zasadzie:

Zasada indukcji matematycznej. Jeżeli

  1. istnieje taka liczba naturalna n0, że T(n0) jest zdaniem prawdziwym,

  2. dla każdej liczby naturalnej n n0 prawdziwa jest implikacja T(n) T(n + 1),

to T(n) jest zdaniem prawdziwym dla każdej liczby naturalnej n n0.

Przykład: Udowodnić, że dla każdej liczby naturalnej n 3 spełniona jest nierówność

2n > 2n.

Nierówność jest tu formą zdaniową T(n), n0 = 3.

1. Dla n = 3 nierówność jest prawdziwa, ponieważ 23 = 8 > 2 . 3 = 6. T(3) jest więc zdaniem prawdziwym.

2. Załóżmy, że nierówność jest prawdziwa dla liczby naturalnej n 3. Mnożąc tę nierówność obustronnie przez 2 dostajemy 2 . 2n > 2 . 2n, czyli 2n+1 > 2n + 2n. Ponieważ dla każdego n 3 mamy 2n > 2, więc 2n + 2n > 2n + 2 = 2(n + 1). Stąd ostatecznie

2n+1 > 2(n + 1).

Nierówność ta oznacza prawdziwość zdania T(n + 1). Wykazaliśmy zatem, że dla każdej liczby naturalnej n 3 prawdziwa jest implikacja T(n) T(n + 1), gdyż z prawdziwości jej poprzednika wynika prawdziwość następnika.

Ponieważ założenia zasady indukcji matematycznej są dla nierówności spełnione, więc ta nierówność jest prawdziwa dla każdego n 3.

Dowód przeprowadzony metodą indukcji matematycznej nazywamy dowodem indukcyjnym; składa się on z dwóch etapów:

1. sprawdzenia, że T(n0) jest prawdziwe,

2. dowodu, że dla każdego n n0 jeżeli T(n) jest prawdziwe, to T(n + 1) jest prawdziwe.

Ten drugi etap nazywamy krokiem indukcyjnym; zakładamy w nim, że dla liczby naturalnej n n0 zdanie T(n) jest prawdziwe (tzw. hipoteza indukcyjna) i na tej podstawie dowodzimy prawdziwości zdania T(n + 1).

Oto jeszcze jeden przykład:

Przykład: Udowodnić, że dla każdego naturalnego n

12 +22 +...+ n2 = (n + 1)(2n + 1).

Dowód indukcyjny, n0 = 1.

1. Sprawdzamy, że równość jest prawdziwa dla n = 1:

12 = (1 + 1)(2 . 1 + 1) = 1.

2. Załóżmy, że równość jest prawdziwa dla liczby naturalnej n. Do obu stron tej równości dodajemy (n + 1)2, więc

12 +22 +...+ n2 + (n + 1)2 = (n + 1)(2n + 1) + (n + 1)2

a następnie przekształcamy prawą stronę:

(n+1)(2n+1)+(n+1)2=[n(2n+1)+6(n+1)]=
 

Stąd

12 +22 +...+ n2 + (n + 1)2 = [(n + 1) + 1] . [2(n + 1) + 1].

Ta równość różni się od równości, którą chcemy dowieść tylko tym, że mamy w niej n + 1 zamiast n. Dla każdej liczby naturalnej n prawdziwa jest więc implikacja T(n) T(n + 1), gdzie T(n) oznacza dowodzoną równość. Na mocy zasady indukcji matematycznej równość jest więc prawdziwa dla każdej liczby naturalnej n.

Za pomocą zasady indukcji matematycznej łatwo i szybko dowodzi się cały szereg charakterystycznych twierdzeń. Podajemy niektóre z nich.

Sumy potęg kolejnych liczb naturalnych.

  1. k = = s1

  2. k2 = = s2 (patrz powyższy przykład)

  3. k3 = s12

  4. k4 = s2(3n2 + 3n - 1)

  5. k5 = s12(2n2 + 2n - 1)

  6. k6 = s2(3n4 +6n3 - 3n + 1)

  7. k7 = s12(3n4 +6n3 - n2 - 4n + 2)

  8. k8 = s2(5n6 +15n5 +5n4 -15n3 - n2 + 9n - 3)

Sumy potęg kolejnych nieparzystych liczb naturalnych.

  1. (2k - 1) = n2 =

  2. (2k - 1)2 = n(4n2 -1) =

  3. (2k - 1)3 = (2n2 - 1)

  4. (2k - 1)4 = (12n2 - 7)

  5. (2k - 1)5 = (16n4 -20n2 + 7)

  6. (2k - 1)6 = (48n4 -72n2 + 31)

Podzielność.

  1. 2| n2 - n

  2. 6| n3 - n

  3. 30| n5 - n

  4. 42| n7 - n

  5. 546| n13 - n

  6. 9| 10n - 1

  7. 12| 10n - 4

  8. 11| 10n - (- 1)n

  9. 101| 102n - (- 1)n

  10. 1001| 103n - (- 1)n

  11. 7| 103n+1 -3(- 1)n

  12. 13| 103n+1 +3(- 1)n

  13. 14| 103n+2 -2(- 1)n

  14. 52| 103n+2 +4(- 1)n

  15. 11| 26n+1 +32n+2

  16. 10| 22n - 6

  17. 41| 5 . 72(n+1) +23n

  18. 25| 2n+23n + 5n - 4

  19. 169| 33n - 26n - 1

  20. 11| 55n+1 +45n+2 +35n

Nierówność Bernoulliego, jej uogólnienia i zastosowania.

  1. (1 + a)n 1 + na, a > - 1 (Bernoulli, 1689)

  2. (1 + a)n 1 + na + a2, a 0

  3. (1 + a)n 1 + na + a2 + a3, a > - 1

  4. (1 + a)1/n 1 + , a > - 1

  5. (1 + a)1+1/n 1 + , a > - 1

  6. (1 + a)1+1/n 1 + (1 + )a, a > - 1

  7. (1 + a)1+m/n 1 + (1 + )a, a > - 1

  8. (1 + a)p/q 1 + a, a > - 1, p q 1

  9. (1 + a)p/q 1 + a, a > - 1, 1 p q

Ciąg Fibonacciego. Określamy

u0 = 0,   u1 = 1,

un+2 = un + un+1

  1. uk = un+2 - 1

  2. u2k+1 = u2n+2

  3. u2k = u2n+1 - 1

  4. (- 1)kuk = u2n-1 - 1

  5. (- 1)k+1uk = u2n + 1

  6. uk2 = unun+1

  7. ukuk+1 = u2n2

  8. un-1un+1 - un2 = (- 1)n

  9. un+1 = umun-m + um+1un-m+1, n m 0

  10. u2n+1 = un2 + un+12

  11. u2n = un+12 - un-12

  12. u3n = un3 + un+13 - un-13

  13. un4 = 1 + un-2un-1un+1un+2

  14. = -

  15. un = , gdzie i są różnymi pierwiastkami równania

x2 = x + 1.


Wyszukiwarka

Podobne podstrony:
3 indukcja matematyczna
indukcja matematyczna
Indukcja matematyczna, Indukcja matematyczna
Indukcja matematyczna, Indukcja matematyczna
Indukcja matematyka dyskretna
3 Indukcja matematyczna, ciągi granice
AMI 04 2 Indukcja matematyczna
lista indukcja matematyczna
Lista 1 indukcja matematyczna
Indukcja matematyczna i niezmie Nieznany
indukcja matematyczna
AMI 04 4 Dowodzenie metodą indukcji matematycznej
indukcja matematyczna, dwumian Newtona zadania
AMI 04 3 Indukcja matematyczna
13 Indukcja matematyczna
1 Liczby naturalne i zasada indukcji matematycznej
AMI 04 4 Dowodzenie metodą indukcji matematycznej

więcej podobnych podstron