Читать книгу Wprowadzenie do teorii obliczeń - Michael Sipser - Страница 31

Dowód indukcyjny jest zaawansowaną metodą wykazywania, że wszystkie elementy pewnego nieskończonego zbioru mają określoną własność. Na przykład możemy użyć dowodu indukcyjnego dla wykazania, że pewne wyrażenie arytmetyczne oblicza pożądaną wartość dla każdego przypisania zmiennych albo że program działa poprawnie we wszystkich krokach lub dla wszystkich wartości wejściowych.

Aby zilustrować, jak przebiega dowód indukcyjny, przyjmijmy zbiór nieskończony jako zbiór liczb naturalnych N = {1, 2, 3, …}, zaś badaną własność nazwiemy P. Naszym celem jest wykazanie, że P(k) jest prawdą dla każdej liczby naturalnej k. Mówiąc inaczej, chcemy udowodnić, że P(1) jest prawdą, podobnie jak P(2), P(3), P(4) i tak dalej.

Każdy dowód indukcyjny składa się z dwóch części, kroku podstawowego (bazy indukcji) oraz kroku indukcyjnego. Każda z tych części jest indywidualnym dowodem. W kroku podstawowym udowadniamy, że P(1) jest prawdziwe. Krok indukcyjny dowodzi, że dla każdego i ≥ 1, jeśli P(i) jest prawdziwe, to prawdziwe jest także P(i + 1).

Po udowodnieniu obu części uzyskujemy pożądany wynik – konkretnie to, że P(i) jest prawdziwe dla każdego i. Dlaczego? Po pierwsze wiemy, że P(1) jest prawdziwe, gdyż udowodniliśmy to w kroku podstawowym. Po drugie wiemy, że P(2) jest prawdziwe, gdyż krok indukcyjny dowodzi, że jeśli P(1) jest prawdziwe, to P(2) jest prawdziwe, a wiemy już, że P(1) jest prawdziwe. Po trzecie wiemy, że P(3) jest prawdziwe, gdyż krok indukcyjny dowodzi, że jeśli P(2) jest prawdziwe, to P(3) jest prawdziwe, a wiemy już, że P(2) jest prawdziwe. Proces ten kontynuujemy dla wszystkich liczb naturalnych, wykazując, że P(4) jest prawdziwe, P(5) jest prawdziwe i tak dalej.

Po zrozumieniu poprzedniego akapitu można łatwo stosować warianty i uogólnienia tej metody. Na przykład krok podstawowy nie musi się koniecznie zaczynać od 1; możemy rozpoczynać od dowolnej wartości b. W takim przypadku dowód indukcyjny wykaże, że P(k) jest prawdziwe dla każdego k nie mniejszego od b.

W kroku indukcyjnym założenie, że P(i) jest prawdziwe, nazywamy hipotezą indukcyjną (założeniem indukcyjnym). Niekiedy użyteczne jest użycie silniejszej hipotezy indukcyjnej stwierdzającej, że P(j) jest prawdziwe dla każdego j ≤ i. Dowód indukcyjny nadal będzie działać, gdyż kiedy chcemy wykazać, że P(i + 1) jest prawdziwe, udowodniliśmy już, że prawdziwe jest P(j) dla każdego j ≤ i.

Format zapisywania dowodów indukcyjnych jest następujący:

Krok podstawowy: Udowadniamy, że P(1) jest prawdą.

⋮

Krok indukcyjny: Dla każdego i ≥ 1 zakładamy, że P(i) jest prawdą, po czym wykorzystujemy to założenie, aby wykazać, że P(i + 1) jest prawdą.

⋮

Udowodnimy teraz przez indukcję poprawność formuły używanej do obliczania wielkości miesięcznych rat kredytów hipotecznych. Przy kupowaniu domu wiele osób pożycza część pieniędzy potrzebnych na zakup, po czym spłaca ten dług przez określoną liczbę lat. Warunki spłaty przewidują, że ustalona kwota jest płacona każdego miesiąca na pokrycie odsetek, jak również jako część oryginalnej sumy, tak że całość zostaje spłacona np. w ciągu 30 lat. Wzór na obliczenie wielkości miesięcznych rat jest okryty tajemnicą, ale w istocie jest całkiem prosty. Dotyczy codziennych spraw wielu ludzi, zatem powinien być interesujący. Użyjemy indukcji, aby udowodnić jego poprawność, co zapewni dobrą ilustrację tej techniki.

Na początek określimy nazwy i znaczenie kilku zmiennych. Niech P będzie kapitałem, czyli sumą oryginalnej pożyczki. Niech I > 0 będzie roczną stopą oprocentowania kredytu, gdzie I = 0.06 oznacza oprocentowanie 6%. Niech Y będzie ratą miesięczną. Dla wygody użyjemy I do zdefiniowania zmiennej M, czyli mnożnika miesięcznego. Jest to stopa zmian kredytu każdego miesiąca z powodu naliczania odsetek. Zgodnie ze standardową praktyką bankowości miesięczna stopa oprocentowania jest jedną dwunastą stopy rocznej, czyli M = 1 + I/12, zaś odsetki naliczane są co miesiąc (miesięczna kapitalizacja).

Każdego miesiąca występują dwie rzeczy. Po pierwsze wielkość kredytu ma skłonność do wzrostu z powodu miesięcznego mnożnika. Po drugie wielkość ta zmniejsza się z powodu miesięcznej spłaty. Niech P_t będzie wielkością kredytu pozostałą do spłacenia po t-tym miesiącu. Przy tej konwencji P₀ = P jest oryginalnym kredytem, P₁ = MP₀ − Y jest wielkością kredytu po jednym miesiącu, P₂ = MP₁ − Y wielkością po dwóch miesiącach. Teraz jesteśmy gotowi sformułować i udowodnić przez indukcję po t twierdzenie podające wzór na wartości P_t.

Twierdzenie 0.25

Dla każdego t ≥ 0 zachodzi