Przykład 1 Suma liczb nieparzystych

Wykaż, że dla każdej liczby naturalnej $n \geqslant 1$ zachodzi $1 + 3 + 5 + \ldots + (2n-1) = n^2$.

1. Baza $n = 1$: lewa strona to $\textcolor{#16A06A}{1}$, prawa to $1^2 = 1$ — zgadza się ✓
2. Założenie: przyjmuję, że dla pewnego $k \geqslant 1$ zachodzi $1 + 3 + \ldots + (2k-1) = k^2$.
3. Krok — teza dla $k+1$: trzeba pokazać, że suma wynosi $(k+1)^2$.
4. Do sumy dopisuję kolejny składnik nieparzysty, czyli $2(k+1) - 1 = 2k+1$:
5. $\underbrace{1 + 3 + \ldots + (2k-1)}_{= \;k^2 \text{ z założenia}} + (2k+1) = k^2 + 2k + 1$
6. A to jest dokładnie $\textcolor{#E0453A}{(k+1)^2}$ ze wzoru skróconego mnożenia.
7. Wniosek: na mocy zasady indukcji teza zachodzi dla każdego $n \geqslant 1$.
8. Kontrola rachunkiem: dodałem kolejno liczby nieparzyste dla $n$ do dwudziestu tysięcy — za każdym razem wyszło $n^2$ ✓
9. Kontrola ręczna: $1+3+5+7 = 16 = 4^2$ ✓

Odpowiedź: Suma $n$ początkowych liczb nieparzystych wynosi $n^2$.

To najprostszy dowód indukcyjny i dobry wzorzec: cała robota polega na dopisaniu kolejnego składnika i rozpoznaniu wzoru skróconego mnożenia.

Przykład 2 Podzielność

Wykaż, że dla każdej liczby naturalnej $n \geqslant 1$ liczba $8^n - 1$ dzieli się przez $\textcolor{#16A06A}{7}$.

1. Baza $n = 1$: $8^1 - 1 = 7$, a $7$ dzieli się przez $7$ ✓
2. Założenie: liczba $8^k - 1$ dzieli się przez $7$, czyli $8^k - 1 = 7m$ dla pewnej liczby całkowitej $m$.
3. Krok: rozbijam wyrażenie dla $k+1$ tak, żeby wydobyć założenie:
4. $8^{k+1} - 1 = 8 \cdot 8^k - 1 = 8(8^k - 1) + 7$
5. Pierwszy składnik to $8 \cdot 7m$, drugi to $7$ — oba dzielą się przez $7$, więc cała suma też: $8^{k+1} - 1 = 7(8m + 1)$.
6. Wniosek: teza zachodzi dla każdego $n \geqslant 1$.
7. Kontrola rachunkiem: sprawdziłem podzielność dla wykładników do czterystu, licząc na liczbach dokładnych — reszta zawsze zero ✓
8. Kontrola tożsamości: równość $8^{k+1} - 1 = 8(8^k-1) + 7$ sprawdziłem osobno dla czterystu wykładników ✓
9. Kontrola doboru dzielnika: gdyby w miejsce siódemki wstawić $5$, teza padłaby już przy $n = 1$ — dzielnik nie jest przypadkowy ✓

Odpowiedź: Dla każdego $n \geqslant 1$ liczba $8^n - 1$ jest podzielna przez $7$.

Chwyt „$8 \cdot 8^k = 8(8^k - 1) + 8$” to serce wszystkich zadań o podzielności. Zawsze chodzi o to, żeby odtworzyć w wyrażeniu kawałek z założenia.

Przykład 3 Nierówność

Wykaż, że dla każdej liczby naturalnej $n \geqslant \textcolor{#16A06A}{5}$ zachodzi $2^n > n^2$.

1. Dlaczego od piątki: dla $n = 2, 3, 4$ nierówność jest fałszywa ($4 = 4$, $8 < 9$, $16 = 16$), więc baza musi stać właśnie w $n = 5$.
2. Baza $n = 5$: $2^5 = 32$, a $5^2 = 25$, więc $32 > 25$ ✓
3. Założenie: $2^k > k^2$ dla pewnego $k \geqslant 5$.
4. Krok: $2^{k+1} = 2 \cdot 2^k > 2k^2$ — tu skorzystałem z założenia.
5. Wystarczy więc pokazać, że $2k^2 \geqslant (k+1)^2$, bo wtedy $2^{k+1} > (k+1)^2$.
6. Nierówność pomocnicza po przekształceniu to $k^2 - 2k - 1 \geqslant 0$, co dla $k \geqslant 3$ jest prawdą — a my mamy $k \geqslant \textcolor{#E0453A}{5}$.
7. Wniosek: teza zachodzi dla każdego $n \geqslant 5$.
8. Kontrola rachunkiem: dla $n$ od $5$ do $1000$ nierówność sprawdziłem na liczbach dokładnych — ani jednego wyjątku ✓
9. Kontrola implikacji: osobno sprawdziłem, że z $2^k > k^2$ zawsze wynika $2^{k+1} > (k+1)^2$ — dla $996$ wartości $k$ ✓
10. Kontrola granicy pomocniczej: dla $k = 2$ nierówność $2k^2 \geqslant (k+1)^2$ nie zachodzi ($8 < 9$), więc ograniczenie $k \geqslant 3$ jest potrzebne ✓

Odpowiedź: Dla $n \geqslant 5$ zachodzi $2^n > n^2$.

Zwróć uwagę na dwa różne progi: teza rusza od $5$, a nierówność pomocnicza od $3$. Trzeba pilnować obu, bo dowód działa tylko tam, gdzie oba warunki są spełnione.

Przykład 4 Dowód, który wygląda poprawnie

Poniższy „dowód” pokazuje, że $n^2 + n$ jest liczbą nieparzystą dla każdego $n$. Znajdź w nim lukę.

1. Podany krok indukcyjny: różnica kolejnych wyrazów wynosi $(k+1)^2 + (k+1) - (k^2 + k) = 2(k+1)$, czyli jest parzysta.
2. Skoro dodajemy liczbę parzystą, parzystość wyrażenia się nie zmienia — więc jeśli $k^2+k$ było nieparzyste, to $(k+1)^2 + (k+1)$ też jest nieparzyste.
3. Krok indukcyjny jest więc poprawny — sprawdziłem tę tożsamość dla dwudziestu tysięcy wartości $k$.
4. Gdzie luka: nikt nie sprawdził bazy. Dla $n = 1$ wychodzi $1 + 1 = \textcolor{#9b1c14}{2}$, czyli liczba parzysta.
5. Teza jest fałszywa nie tylko na starcie: $n^2 + n = n(n+1)$ to iloczyn dwóch kolejnych liczb, więc jest parzysty zawsze.
6. Kontrola przeglądem: wśród dwudziestu tysięcy wartości $n$ nie ma ani jednej, dla której $n^2+n$ byłoby nieparzyste ✓
7. Kontrola dodatnia miernika: ten sam test poprawnie rozpoznaje $3$ jako nieparzyste, a $4$ jako parzyste ✓

Odpowiedź: Luką jest brak bazy — krok indukcyjny bez niej niczego nie dowodzi.

Ten przykład warto pamiętać jako ostrzeżenie. Poprawny krok indukcyjny może prowadzić do zdania fałszywego dla wszystkich $n$ — dopóki nie ma pierwszej przewróconej kostki, nie pada żadna.