Prove by induction that $3^{2n+3}+40n-27$ is divisible by 64 for all n in natural numbers

I cannot complete the third step of induction for this one. The assumption is $3^{2n+3}+40n-27=64k$, and when substituting for $n+1$ I obtain $3^{2n+5}+40n+13=64k$. I've tried factoring the expression, dividing, etc. but I cannot advance from here.

Solution 1:

First, show that this is true for $n=1$:

$3^{2+3}+40-27=64\cdot4$

Second, assume that this is true for $n$:

$3^{2n+3}+40n-27=64k$

Third, prove that this is true for $n+1$:

$3^{2(n+1)+3}+40(n+1)-27=$

$9\cdot(\color\red{3^{2n+3}+40n-27})-320n+256=$

$9\cdot\color\red{64k}-320n+256=$

$576k-320n+256=$

$64\cdot(9k-5n+4)$

Please note that the assumption is used only in the part marked red.

Solution 2:

Many inductive proofs of this and similar divisibilities boil down to computing the first two terms of the Binomial Theorem $\,\color{#0a0}{\rm BT}.\,$ However, this innate structure is often (greatly) obfuscated by details of the special case. Let's bring this structure to the fore and exploit it to the hilt. Doing so we will see how it greatly simplifies the inductive proof - so much so that the proof becomes obvious, and the arithmetic becomes so easy that it can all be done mentally.

$ {\rm mod}\,\ \color{#c00}{8^2}\!:\,\ \ \overbrace{27 (1\!+\!8)^n}^{\large 3^{\LARGE 3\,+\,2n}} \,\overset{\color{#0a0}{\rm\large BT_{\phantom |}\!}}\equiv {27(1\!+\!8n)} \equiv \!\!\!\!\!\!\!\!\overbrace{27\!+\!24n}^{\large -(-27\,+\,40n)\ \ \quad }\!\!\!\!\! $ by $\,\ 27(8)\equiv \overbrace{{(3\!+\!3\!\cdot\! \color{#c00}8)}\color{#c00}8 \equiv 3\cdot8}^{\large \color{#c00}{8^{\Large 2}}\,\equiv\, 0}\,$

The inductive step of $\,\color{#0a0}{\rm BT}\,$ is much clearer without obfuscation by special-case cruft, viz.

$\!\begin{align}{\rm mod}\,\ \color{#c00}{a^2}\!:\ \ (1+ a)^{\large n}\ \ \ \ \equiv&\,\ \ 1 + na\qquad\qquad\ \ \ \ \,{\rm i.e.}\ \ P(n)\\[1pt] \Rightarrow\ \ \ (1+a)^{\color{}{\large n+1}}\! \equiv &\ (1+na)(1 + a)\ \ \ \ \ \ \ {\rm by}\ \ 1+a \ \ \rm times\ prior\\[2pt] \equiv &\,\ \ 1+ na+a+n\,\color{#c00}{a^2}\\[2pt] \equiv &\,\ \ 1\!+\! (n\!+\!1)a\qquad\quad\ \, {\rm i.e.}\ \ P(\color{}{n\!+\!1})\\ \end{align}$

More generally the same idea yields a proof of the following

Theorem $\ \ \forall n\in\Bbb N\!:\ d\mid f(n) = a^n\! + bn + c \iff d\mid \color{}{(a\!-\!1)^2},\, \color{}{a\!+\!b\!-\!1},\, \color{}{1\!+\!c}$

Solution 3:

HINT: $$\begin{align} & 3^{2n+5}+40n+13 \\ &=9\cdot 3^{2n+3}+9\cdot 40n -9\cdot 27 - 8\cdot 40n+256 \\ & =9(3^{2n+3}+40n -27) - 64\cdot 5n+ 64\cdot 4\end{align}$$