Question 889703
We induct on n. n = 1 is trivial (3^4 - 8 - 9 = 64).


Assume *[tex \large 3^{2k+2} - 8k - 9 \equiv 0 \pmod {64} ] for some integer *[tex \large k \ge 1]. Then *[tex \large 3^{2k+2} \equiv 8k+9 \pmod{64}].


We want to show that *[tex \large 3^{2(k+1) + 2} - 8(k+1) - 9 \equiv 0 \pmod{64}]. This is equivalent to showing that *[tex \large 9 \times 3^{2k+2} - 8k - 17 \equiv 0 \pmod{64}]. However, since we know that *[tex \large 3^{2k+2} \equiv 8k+9], the statement we wish to prove is equivalent to *[tex \large 9 \times (8k+9) - 8k - 17 \equiv 0 \pmod{64}], which is true since the LHS equals *[tex \large 64k + 64]. The induction is complete and the statement holds for all positive integers n.