1 +2 + 2² + 2³ + ... + 2^n = 2^(n +1) - 1 1⁰ dla n = 1 równośc jest prawdziwa, bo 1 + 2¹ = 3 = 2^(1+1) - 1 = 2² - 1 - 4 - 1 = 3 2⁰ Załóżmy, że równość jest prawdziwa dla liczby naturalnej n > 1, czyli 1 + 2¹ + 2² + 2³ + ... + 2^n = 2^(n +1) - 1 ----------------------------------------------------- Sprawdzimy prawdziwość implikacji T(n) => T(n +1) dla każdej liczby n > 1 Mamy [1 + 2¹ + 2² + 2³ + ... + 2^n] + 2^(n +1) = 2^(n +1) - 1 + 2^(n +1) = = 2* 2 ^(n +1) -1 = 2^{(n +1) +1] - 1 Wykazaliśmy zatem , ze dla kadej liczby naturalnej n > 1 prawdziwa jest implikacja T(n) => T( n +1).gdyż z prawdziwości jej poprzednika wynika prawdziwość następnika. Ponieważ założenia 1⁰ i 2⁰ zasady indukcji matematycznej są dla danej równości spełnione, więć ta równość jest prawdziwa dla dowolnej liczby n > 1. cnu. ===========
UWAGA: błędny zapis prawej strony! Powinno być: 1 + 2 + 2² + 2³ +...+ 2^n = 2^(n+1) - 1 (ewentualnie jeszcze dokładniej: ... = (2^(n+1)) - 1 (Przy (2^n+1) równość jest nieprawdziwa!) __________________________ A oto rozwiązanie: I Dla n = 1: 1 + 2 = 2^(1+1) - 1 3 = 3 -- równość jest prawdziwa. II [n ===> (n+1)] (jeśli równość jest prawdziwa dla n -- to będzie prawdziwa dla n+1) Podstawiamy k zamiast n: [A] 1 + 2 + 2² + 2³ +...+ 2^k = 2^(k+1) - 1 Podstawiamy (k + 1) zamiast n: [B] 1 + 2 + 2² + 2³ +...+ 2^k + 2^(k+1) = 2^((k+1)+1) - 1 Ponieważ zakładamy prawdziwość równości dla n = k [A], więc wykorzystamy równość [A] podstawiając w [B] zamiast wszystkich wyrazów z wyjątkiem ostatniego -- prawą stronę [A]: [C] 2^(k+1) - 1 + 2^(k+1) = 2^((k+1)+1) - 1 Ponieważ 2^m + 2^m = 2 * 2^m = 2^(m+1), (-- dodawanie jednakowych składników, a potem mnożenie potęg o jednakowych podstawach) więc zastosujmy to przy m = k+1 w [C]: [D] 2^((k+1)+1) - 1 = 2^((k+1)+1) - 1 czyli ostatecznie (już nawet bez wykonywania dalszych obliczeń i uproszczeń) L = P a więc III Równość jest prawdziwa dla dowolnego n.
