Indukcja matematyczna - podzielność 4ⁿ + 5 przez 3

Krok 1. Sprawdzenie dla n = 1 (baza). $4^1 + 5 = 9 = 3 \cdot 3$ - dzieli się przez $3$.

Krok 2. Założenie i teza. Zakładamy, że dla pewnego $k \ge 1$ zachodzi $4^k + 5 = 3m$, gdzie $m$ jest liczbą całkowitą. Teza: $3 \mid 4^{k + 1} + 5$.

Krok 3. Dowód kroku. Zapisujemy wyrażenie dla $k + 1$ tak, by pojawiło się w nim $4^k + 5$:

$4^{k + 1} + 5 = 4 \cdot 4^k + 5 = 4\left(4^k + 5\right) - 20 + 5 = 4\left(4^k + 5\right) - 15.$

Z założenia $4^k + 5 = 3m$, więc

$4^{k + 1} + 5 = 12m - 15 = 3(4m - 5).$

Liczba $4m - 5$ jest całkowita, zatem $4^{k + 1} + 5$ dzieli się przez $3$.

Odpowiedź. Na mocy zasady indukcji matematycznej $3 \mid 4^n + 5$ dla każdego $n \ge 1$.

Uwaga: mnożąc założenie przez $4$, dostajemy $4 \cdot 5 = 20$ zamiast $5$ - trzeba więc odjąć $15$. Kluczowe jest to, że $15$ też dzieli się przez $3$; gdyby różnica nie była wielokrotnością $3$, krok by nie przeszedł.