Indukcja matematyczna - podzielność 3²ⁿ⁺² − 8n − 9 przez 64

Krok 1. Sprawdzenie dla n = 1 (baza). $h(1) = 3^4 - 8 - 9 = 81 - 17 = 64$ - dzieli się przez $64$.

Krok 2. Założenie i teza. Zapiszmy $3^{2n + 2} = 9^{n + 1}$, czyli $h(n) = 9^{n + 1} - 8n - 9$. Zakładamy, że $64 \mid h(k)$ dla pewnego $k \ge 1$. Teza: $64 \mid h(k + 1)$, gdzie

$h(k + 1) = 9^{k + 2} - 8(k + 1) - 9 = 9 \cdot 9^{k + 1} - 8k - 17.$

Krok 3. Dowód kroku. Chcemy zobaczyć w $h(k + 1)$ wyrażenie $9 \cdot h(k)$. Ponieważ

$9 \cdot h(k) = 9 \cdot 9^{k + 1} - 72k - 81,$

to $9 \cdot 9^{k + 1} = 9h(k) + 72k + 81$. Podstawiamy:

$h(k + 1) = 9h(k) + 72k + 81 - 8k - 17 = 9h(k) + 64k + 64 = 9h(k) + 64(k + 1).$

Składnik $9h(k)$ dzieli się przez $64$ z założenia, a $64(k + 1)$ jest wielokrotnością $64$. Zatem $64 \mid h(k + 1)$.

Odpowiedź. Na mocy zasady indukcji matematycznej $64 \mid 3^{2n+2} - 8n - 9$ dla każdego $n \ge 1$. Dla sprawdzenia: $h(2) = 729 - 25 = 704 = 64 \cdot 11$.