n∑ i2i=0Wyjątkiem jest dodatkowy składnik sumy w równaniu (2...

3) dla i = n+1, czyli 2n+1.
Ponieważ można założyć, że w dowodzie równania (2.3) hipoteza indukcyjna S(n) jest praw-
dziwa, należy znaleźć sposób na wykorzystanie S(n) w dalszych rozważaniach. Można to osiągnąć,
rozbijając sumę z równania (2.3) na dwie części, z których jedną jest suma znana z równania dla
S(n). Oznacza to oddzielenie ostatniego składnika, dla i = n+1, i zapisanie:
n 1
+
n
i
i
n 1
2 =
2 + 2 +
∑ ∑
(2.4)
i=0
i=0
n
Teraz można wykorzystać równania S(n), zastępując po prawej stronie równania (2.4) sumę ∑
i
2
i=0
wyrażeniem 2n+1–1:
n 1
+
i
n 1
+
1
2 = 2
−1+ 2 +
∑
n
(2.5)
i=0
Po uproszczeniu prawej strony równania (2.5) otrzymujemy 2×2n+1–1, czyli 2n+2–1. Widać teraz,
że suma po lewej stronie równania (2.5) jest identyczna z sumą po lewej stronie równania (2.3), zaś
prawa strona równania (2.5) jest równa prawej stronie równania (2.3). Dowodzi to zatem poprawności
równania (2.3) przy wykorzystaniu równania S(n); dowód ten jest właśnie krokiem indukcyjnym.
Wniosek jest taki, że twierdzenie S(n) jest prawdziwe dla wszystkich nieujemnych wartości n.
Uzasadnienie poprawności dowodzenia przez indukcję
W dowodzie indukcyjnym najpierw należy dowieść, że twierdzenie S(0) jest prawdziwe. Następnie
należy wykazać, że jeśli twierdzenie S(n) jest prawdziwe, to prawdziwe jest także twierdzenie S(n+1).
Pojawia się jednak pytanie, dlaczego można przyjąć, że S(n) jest prawdziwe dla wszystkich n ≥ 0?
Poniżej zostaną pokazane dwa „dowody”. Matematyk powiedziałby, że oba prezentowane „dowody”
prawidłowości dowodzenia indukcyjnego same wymagają dowodów indukcyjnych, nie są więc żad-
nymi dowodami. Indukcję należy zaakceptować jako aksjomat. Mimo to, wielu Czytelników po-
winno uznać poniższe rozważania za pomocne.
Poniżej zakłada się, że wartością podstawową jest n = 0. Oznacza to, że wiadomo, iż S(0) jest
prawdziwe, oraz że dla wszystkich n większych od 0, jeśli S(n) jest prawdziwe, to prawdziwe jest
także S(n+1). Tę samą argumentację można wykorzystać dla wartości podstawowej będącej do-
wolną inną liczbą całkowitą.
„Dowód” pierwszy: iteracja kroku indukcyjnego. Przypuśćmy, że chcemy wykazać, że twierdze-
nie S(a) jest prawdziwe dla konkretnej nieujemnej liczby całkowitej a. Jeśli a = 0, należy po prostu
odwołać się do prawdziwość podstawy, S(0). Jeśli a > 0, argumentacja przedstawia się następująco.
54
2. ITERACJA, INDUKCJA I REKURENCJA
Zastępowanie zmiennych
Dla wielu osób zastępowanie zmiennych, tak jak n w równaniu S(n), wyrażeniem zawierającym
tę samą zmienną stanowi pewien problem. Przykładowo, powyżej za zmienną n podstawiono
zmienną n+1 w twierdzeniu S(n) z równania (2.3). Aby tego dokonać, należało najpierw ozna-
czyć wszystkie wystąpienia zmiennej n w S. Metodą ułatwiającą tego typu operację jest za-
stąpienie wszystkich wystąpień zmiennej n jakąś nową zmienną, np. m, dzięki czemu można
całkowicie pozbyć się zmiennej n w twierdzeniu S. Przykładowo, równanie dla S(n) wyglą-
dałoby następująco:
m
2i = 2 1
+ −1
∑ m
i=0
Następnie należy zastąpić każde wystąpienie zmiennej m wyrażeniem n+1. W efekcie otrzymu-
jemy równanie:
n 1
+
2i = 2( + )1 1
+ −1
∑
n
i=0
Po uproszczeniu (n+1)+1 do n+2 otrzymamy równanie (2.3).
Warto zauważyć, że należy umieszczać wstawiane wyrażenie w nawiasach w celu unik-
nięcia przypadkowej zmiany kolejności działań. Przykładowo, gdyby zamieniono m na n+1
w wyrażeniu 2×m, nie umieszczając wstawianego wyrażenia n+1 w nawiasach, otrzymano by
2×n+1, zamiast prawidłowego wyrażenia 2×(n+1), czyli 2×n+2.
Z podstawy wiadomo, że S(0) jest prawdziwe. Stwierdzenie „S(n) implikuje S(n+1)” dla wartości
0 podstawionej w miejsce n przyjmuje formę „S(0) implikuje S(1)”. Ponieważ wiadomo, że S(0)
jest prawdziwe, wiadomo także, że S(1) jest prawdziwe. Podobnie, jeśli zamieni się n na 1, otrzy-
mując zdanie „S(1) implikuje S(2)”, wiadomo, że S(2) również jest prawdziwe. Zamiana n na 2 daje
zdanie „S(2) implikuje S(3)”, zatem S(3) jest prawdziwe, itd. Nie ma znaczenia, jaka jest wartość a,
w końcu dochodzi się do twierdzenia S(a), co kończy dowód.
„Dowód” drugi: najmniejszy kontrprzykład. Przypuśćmy, że twierdzenie S(n) nie było praw-
dziwe dla przynajmniej jednej wartości n. Niech a będzie najmniejszą nieujemną liczbą całkowitą,
dla której S(a) jest fałszywe. Jeśli a = 0, stanowi to zaprzeczenie podstawy, S(0), i wiadomo, że a
musi być większe od 0. Jeśli jednak a > 0 i a jest najmniejszą nieujemną liczbą całkowitą, dla której
S(a) jest fałszywe, to S(a–1) musi być prawdziwe. Krok indukcyjny, dla n zastąpionego przez a–1,
mówi teraz, że S(a–1) implikuje S(a). Ponieważ S(a–1) jest prawdziwe, S(a) także musi być praw-
dziwe, co przynosi kolejną sprzeczność. Ponieważ założono, że istnieją nieujemne wartości n, dla
których S(n) jest fałszywe i wywiedziono z tego sprzeczność, S(n) musi być prawdziwe dla do-
wolnego n ≥ 0.
2.3. DOWODY INDUKCYJNE
55
Kody detekcji błędów
Poniżej zostanie przedstawiona analiza rozszerzonego przykładu kodów detekcji błędów, zagad-
nienia interesującego samego w sobie i prowadzącego dodatkowo do ciekawego dowodu induk-
cyjnego. Podczas transmisji danych siecią zwykle koduje się znaki (litery, cyfry, znaki interpunk-
cyjne itd.) do postaci ciągów bitów, czyli zer i jedynek. Poniżej zostało przyjęte założenie, że znaki są reprezentowane za pomocą siedmiu bitów. Powszechnie stosowaną normą jest przesyłanie
większej liczby bitów na znak, ósmy bit może bowiem ułatwić np. wykrywanie prostych błędów
w transmisji danych (może się zdarzyć, że jedno z przesyłanych zer lub jedynek ulegnie zmianie
na skutek zakłóceń transmisji, co powoduje, że do odbiorcy dotrze przeciwny bit — 0 zamiast 1 lub
1 zamiast 0). Mechanizm używania dodatkowego bitu jest więc bardzo przydatny, ponieważ sys-
tem komunikacji może przesłać informację o niepożądanej zmianie jednego z ośmiu przesyłanych
bitów, co umożliwia zainicjowanie procesu ponownej transmisji.
Aby móc wykrywać zmiany za pomocą jednego bitu, należy mieć pewność, że żadna para
znaków nie jest reprezentowana przez sekwencje bitów różniące się od siebie tylko na jednej po-
zycji. W takim przypadku, gdyby ta pozycja została zmieniona, otrzymany zostałby kod zupełnie
innego znaku i nie istniałaby możliwość wykrycia wystąpienia błędu. Przykładowo, jeśli kod pew-