Proof by induction that $ 3^{3n+3}-26n-27$ is divisble by $13^2$ (and $26^2$)

Question

$ 169$ | $3^{3n+3}-26n-27$ ?

Fulfilled for $n=0$. Induction to $n+1$:
An integer $x$ exists so that

$ 169x= 3^{3n+6}-26n-27-26$
$ 169x= 27*3^{3n+3}-26n-27-26$
$ 169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$

An integer $m$ exists so that

$ 169x= 26*3^{3n+3}+169m-26$
($ 13x= 2*(3^{3n+3}-1)+13m$)

Now I'm stuck although it looks simple. Thanks for any input in advance.

Answer 1

This is what you should have done instead: $$\begin{align}27\cdot3^{3n+3}-26n-27-26&=27(3^{3n+3}-26n-27)+27\cdot26n+27\cdot27-26n-27-26\\&=27\cdot169m+26\cdot26n-26\cdot26\end{align}$$

Here's the proof more clearly without unnecessary variables: $$\begin{align}13^2&\mid3^{3(n+1)+3}-26(n+1)-27\\13^2&\mid27\cdot3^{3n+3}-26n-27-26\\13^2&\mid27(3^{3n+3}-26n-27)+26\cdot26n+26\cdot27-26\\13^2&\mid13^2\cdot4n+13^2\cdot4\end{align}$$ You use the induction hypothesis in the 3rd row.

Answer 2

I'm not sure if you are mixing up what is given and what is to be proved - perhaps you are just not writing your working very clearly. For the induction step you have to assume that $$3^{3n+3}-26n-27=169x$$ for some integer $x$, and then you have to prove that $$3^{3n+6}-26n-27-26$$ is $169$ times some integer (not necessarily $x$, just some integer). The best way to do this would be to note that by assumption $$3^{3n+3}=169x+26n+27\ ,$$ and therefore the required expression can be written $$\eqalign{3^{3n+6}-26n-27-26 &=3^3(3^{3n+3})-26n-27-26\cr &=27(169x+26n+27)-26n-27-26\cr &=27\times169x+(27\times26-26)n+(27^2-2\times27+1)\ .\cr}$$ Remembering that $169=13^2$, can you see why this is $169$ times an integer? For the "nicest" proof, see if you can do it without lots of calculations, and in particular without using a calculator.

Answer 3

Hint $\ $ Conceptually, the induction is simply the first two terms of BT = Binomial Theorem

${\rm mod}\,\ 26^2\!:\ \color{#c00}{(1\!+\!26)^{n+1}}\!\equiv 1\!+\!(n\!+\!1)26\equiv \color{#0a0}{26n\!+\!27}\,\Rightarrow\, 13^2\mid26^2\mid \color{#c00}{27^{n+1}}\!\color{#0a0}{-\!26n\!-\!27}$

Remark $ $ For completeness, below is a simple inductive proof of the first two terms of BT, using $\,\color{#0af}{\rm CPR}=$ Congruence Product Rule

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

Generalization $ $ Using the above idea it is easy to generalize, e.g. from this answer

$\!\begin{align}\rm{\bf Theorem}\ \ \forall n\in\Bbb N\!:\ d\mid f(n) = a^n\! + b\:\!n + c &\rm \iff d\mid \color{blue}{(a\!-\!1)^2},\, \color{brown}{a\!+\!b\!-\!1},\, \color{darkorange}{1\!+\!c}\\ &\rm \iff d\mid f(0),\,f(1),\,f(2)\end{align}$

Answer 4

The same, but using modules.

Let's prove by induction that $3^{3n+3} - 26n - 27 \equiv 0 \pmod {169}$

Working with module $169$:

• Base case. If $n = 1$, then $3^3 - 27 \equiv 0$.

• Induction. Let fix an integer $m \geq 0$ and supose that (induction hypothesis): $$3^{3m+3}-26m -27 \equiv 0 \pmod{169}$$ or, with other words: $$3^{3m+3} \equiv 27 + 26m \pmod{169}$$ We want to prove that $$3^{3m+6}-26(m+1) -27 \equiv 0 \pmod{169}$$

---

Prove:

$$\begin{align}3^{3m+6}-26(m+1)-27&\equiv 3^3 \cdot 3^{3m+3} - 26m - 26 -27\\ &\equiv 27 \cdot 3^{3m+3} - 26m -26-27\quad(*)\\ &\equiv 27(27+26m) - 26m - 26 -27\\ &\equiv (702-26)m + (729-27-26)\\ &\equiv 4\cdot 169m + 4 \cdot 169\\ &\equiv 0m + 0 \\ &\equiv 0 \end{align}$$

We have applied induction hypothesis at $(*)$.

So, as we have proved that $3^{3n+3} - 26n - 27 \equiv 0 \pmod {169}$, then, $169 | 3^{3n+3} - 26n - 27$.