Hanna Jasowicz

Wydział Informatyki i Nauki o Materiałach

Kierunek: Informatyka, 2-st magisterskie, zaoczne

Analiza i Złozoność Obliczeniowa Algorytmów

Zadanie 2 Powtórka z indukcji matematycznej

Zadanie

Wartość zwracaną przez poniższą funkcję można opisać równaniem rekurencyjnym:

A(n)

1 if n=0

2 then return 0

3 else if n=1

4 then return 1

5 else return 8 · A(n-1) -7 · A(n-2)

Ułóż to równanie rekurencyjne, a następnie udowodnij przez indukcję, że jego rozwiązaniem jest 7ⁿ - 1

6 .

Rozwiązanie

- Indukcja matematyczna dotyczy własności liczb naturalnych

- Indukcja matematyczna jest niezawodną metodą dowodzenia twierdzeń.

- Takie twierdzenie sprowadza się zazwyczaj do pewnej propozycji A(n), która - jak przypuszczamy odnosi się do zbioru wszystkich liczb całkowitych, lub przynajmniej do pewnego ich podzbioru

(np. dla wszystkich n ≥ n₀ , gdzie n₀ jest pewną ustaloną wartością. Podkreślmy słowo przypuszczamy - metoda indukcja 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 następujących etapów:

1. Wykazujemy słuszność A(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. Ale może być to inna dowolnie ustalona liczba naturalna.

2. Zakładamy, że A(n) jest prawdziwe - zakładamy słuszność A(n) dla n=k

Tworzymy odpowiednie założenie indukcyjne dla n=k

3. W oparciu o to założenie udowadniamy prawdziwość naszego przypuszczenia dla n= n+1, a więc wykazujemy słuszność A(n+1).

A(0) = 0

A(1) = 1

A(n) = 8 · A(n-1) -7 · A(n-2)

Równanie rekurencyjne:

A(n) = 8 · A(n-1) -7 · A(n-2) = 7ⁿ - 1

6

1. sprawdzenie hipotezy dla n=2:

L = 8 · A(2-1) - 7 · A(2-2) = 8 · A(1) - 7 · A(0) = 8 · 1 - 7 · 0 = 8

P = 7² - 1 = 48 : 6 = 8

6

L = P hipoteza sprawdza się

2. Założenie indukcyjne dla n = k

A(k) = 8 · A(k-1) -7 · A(k-2) = 7^k - 1

6

3. Teza indukcyjna

Chcemy pokazać, że skoro założenie jest prawdziwe dla k to będzie także dla k + 1

A(k+1) = 7^k+1 - 1

6

4. Dowód tezy indukcyjnej:

A(k+1) = 8 · A(k +1 - 1) - 7 · A(k+1-2) =

= 8 · A(k) - 7 · A(k-1) =

= 8 · (7^k - 1) - 7 · (7^k-1 - 1) = 8 · 7^k - 8 - 7 · 7^k-1 + 7 =

6 6 6

= 8 · 7^k - 7^k - 1 = 7^k (8 -1) - 1 = 7^k · 7 - 1 = 7^k+1 - 1

6 6 6 6

Ponieważ stwierdziliśmy, że wzór jest prawdziwy dla n = 2, a także z prawdziwości wzoru dla n = k wynika prawdziwość wzoru dla n = k + 1, więc dzięki zasadzie indukcji matematycznej wzór jest prawdziwy dla każdego całkowitego
.

Jeśli równanie jest prawdziwe dla liczby k, to jest ono prawdziwe dla k + 1.

Oznacza to, że jeśli jest ono prawdziwe dla np: n=2 to jest ono prawdziwe dla wszystkich liczb naturalnych.

---