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

Question

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.

Answer 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.

Answer 2

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}$$

Answer 3

Notice that: $$3^{2n+5}+40n+13=9(3^{2n+3}+40n−27)−320n+256.$$

Answer 4

Let $A_n = 3^{2n+3}+40n-27$, then $A_n = 11A_{n-1} - 19A_{n-2} + 9A_{n-3}$.

From this it's clear that if 64 divides $A_n$ three consecutive values of $n$ then it holds for the next. So by induction it's enough to check it for $n = -1,0,1$, which is easy enough to do by hand.

Answer 5

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}$