38. Indukcja matematyczna. Definicje rekurencyjne.

Indukcja matematyczna

Sposób dowodzenia twierdzeń matematycznych, odnoszących się do liczb całkowitych. Takie twierdzenie sprowadza się zazwyczaj do pewnej propozycji P(n), która - jak przypuszczamy odnosi się do zbioru wszystkich liczb całkowitych, lub przynajmniej do pewnego ich podzbioru (np. dla wszystkich
, gdzie n₀ jest pewną ustaloną wartością). Podkreślmy słowo przypuszczamy - metoda indukcyjna nie odkryje nam pewnej własności, ale pozwoli udowodnić taką własność, którą - w oparciu np. o pewne przesłanki ,,empiryczne'' - podejrzewamy o istnienie. Metoda indukcji składa się z dwóch etapów:

1. Wykazujemy słuszność P(n) dla pewnego ustalonego n=n₀. Zwykle n₀ = 1, bo zwykle dowody indukcyjne odnoszą się do całego zbioru dodatnich liczb całkowitych. Dla n₀=1 ewentualne rachunki są też najprostsze.

2. Zakładamy, że P(n) jest prawdziwe i w oparciu o to założenie udowadniamy prawdziwość naszego przypuszczenia dla n= n+1, a więc wykazujemy słuszność P(n+1).

Niech φ (n) będzie pewną funkcją zdaniową określoną na zbiorze liczb naturalnych lub ogólniej na zbiorze liczb całkowitych n ≥ n_o, gdzie n_o jest pewną liczbą całkowitą. Będziemy mówić, że n posiada własność φ jeśli φ(n)≡1 (jest zdaniem prawdziwym). W tym przypadku mówimy również, że własność φ zachodzi (lub jest spełniona) dla liczby całkowitej n.

Zasada indukcji zupełnej, pierwsze sformułowanie

Niech φ będzie pewną własnością dla liczb całkowitych n ≥ n_o, tj. φ(n) jest funkcją zdaniową dla każdego n ≥ n_o. Wówczas jeśli spełnione są następujące warunki:

1. własność φ zachodzi dla n_o, tj. φ(n_o)≡1;

2. jeśli własność φ zachodzi dla liczby n ≥ n_o , to własność φ zachodzi dla liczby n+1, czyli spełniona jest implikacja φ(n)=> φ(n+1)≡1;

to wtedy własność φ zachodzi dla dowolnej liczby n ≥ n_o , czyli:

.

Zasada indukcji zupełnej, drugie sformułowanie

Niech φ będzie pewną własnością dla liczb całkowitych n ≥ n_o , tj. φ(n) jest funkcją zdaniową dla każdego n ≥ n_o. Wówczas jeśli spełnione są następujące warunki:

1. własność φ zachodzi dla n_o, tj. φ(n_o)≡1;

2. jeśli n>n_o i własność φ zachodzi dla każdej liczby n_o ≤ k <n, to własność φ jest spełniona dla φ(n), czyli φ(n)≡1 (dokładnie w całości ozn. To, że implikacja
   )

to wtedy własność φ zachodzi dla dowolnej liczby n ≥ n_o , czyli:

.

Uzasadnienie zasady indukcji zupełnej

Pierwsze sformułowanie

φ(n_o)≡1

φ(n)=> φ(n+1), n ≥ n_o

φ(n-1)=> φ(n), n > n_o

φ(n_o) - n_o ma własność φ

φ(n_o)=> φ(n_o+1)=> φ(n_o+2)=> φ(n_o+3)

φ(n) ≡1

Drugie sformułowanie

n_o≤ k < n_o+1

k=n_o

φ(n_o)=> φ(n_o+1)=>
φ(k)=> φ(n_o+2) φ(n_o), φ(n_o+1)≡1

φ(n_o) ∧ φ(n_o+1)=> φ(n_o+2)

φ(k)=> φ(n_o+3)

φ(n_o) ∧ φ(n_o+1) ∧ φ(n_o+2)=> φ(n_o+3)

φ(n) ≡1

Przykład:

Typowym przykładem metody indukcji może być na przykład wykazanie wzoru na sumę sześcianów pierwszych n dodatnich liczb całkowitych:

(1.3)

Zgodnie ze schematem zaczynamy od ,,sprawdzenia'' hipotezy dla n=1. Mamy

Następnie zakładamy słuszność P(n) dla n=k

(1.4)

i próbujemy udowodnić ją dla n=k+1. dodajemy do obu stron 1.4 (k+1)³:

Definicje rekurencyjne

Rekurencja - odwoływanie się funkcji do samej siebie.

(*)
(suma n - składników)

(I)
, definiowanie symbolu (*) dla n=1

(II) Zakładamy, że symbol
jest określony.

Zależność rekurencyjna
została określona dla liczby n+1∈N.

(np. ciąg arytmetyczny)

(#)
(iloczyn n - składników)

(I)
, definiowanie symbolu (#) dla n=1

(II) Zakładamy, że symbol
jest określony.

Zależność rekurencyjna
została określona dla liczby n+1∈N.

(np. silnia, potęgowanie - a_i=a)

Innym przykładem rekurencji jest ciąg Fibonacciego.

Definicja ciągu Fibonacciego jest rekurencyjna:

fib(0) = 0

fib(1) = 1

fib(n) = fib(n - 1) + fib(n - 2), dla

gdyż definiuje funkcję odwołując się w definicji do niej samej.

Wyrazy ciągu Fibonacciego: 1, 1, 2, 3, 5, 8 , 13, 21, 34, 55, 89, 144, ....

W ciągu tym pierwsze dwa wyrazy są równe jeden, każdy następny wyraz otrzymujemy sumując dwa poprzednie.

---