Divisible by 19 Induction Proof

Question

Prove by induction that for all natural numbers $n$, $\frac{5}{4}8^n + 3^{3n-1}$ is divisible by $19$.

I'm running into trouble at the inductive part of the step, I am currently attempting to add/subtract the inductive hypothesis but I end up with two different coefficients that are seemingly unrelated to $19$. I've been stuck on this for days, thanks for the help!

Answer 1

For $n+1$ step, we have $$\begin{align}\frac 54\cdot 8^{n+1}+3^{3(n+1)-1}&=\frac 54\cdot 8^{n+1}+8\cdot 3^{3n-1} -8\cdot 3^{3n-1}+3^{3n+2}\\&=8\left(\frac 54\cdot 8^n+3^{3n-1}\right)+(3^3-8)\cdot 3^{3n-1}\\&=8\left(\frac 54\cdot 8^n+3^{3n-1}\right)+19\cdot 3^{3n-1}.\end{align}$$

Answer 2

Rewrite as $f(n)=10\cdot 8^{n-1}+3^{3n-1}$ to clear the fraction.

Then can you see that $f(n+1)=10\cdot 8^n+3^{3n+2}=8f(n)+(27-8)3^{3n-1}$

We choose the factor $8$ (we could also have chosen $27$) since we want to get rid of one of the exponentials altogether in the $f(n)$ term, and to find that the other one ends up with a coefficient divisible by $19$.

---

Note that if $f(n)=Aa^n+Bb^n$ then $f(n+1)=(a+b)f(n)-abf(n-1)$ so if $a,b$ are integers and some integer $c$ is a factor of both $f(n-1)$ and $f(n)$ it will also be a factor of $f(n+1)$, which is another way of solving this kind of problem (requires two base cases rather than one, but then the induction goes through).

Answer 3

$\begin{eqnarray}{\bf Hint}\ \ \ {\rm mod}\ 19\!:\,\ \ 3^3\equiv\, 8\ \Rightarrow\ 3^{3n}\!\!&\equiv& 8^n\\ \\ {\rm and}\quad\ 4\,\equiv\, -5\cdot 3\ \Rightarrow\ \dfrac{1}3&\equiv&\!\! {-}\!\!\dfrac{5}4\\ \\ {\rm multiplying \ \, yields}\,\ \ 3^{3n-1}\!&\equiv&\!\! -\!\dfrac{5}4 8^{n}\quad {\bf QED}\end{eqnarray}$

Remark $\ $ As explained here, the proofs in the other answers can be discovered from the above in the following mechanical manner: take the standard proof of the Congruence Product Rule, then substitute the specific numbers in this problem, i.e. simply repeat the proof for the special case at hand. Though many such inductive proofs appear at first glance to be pulled out of a hat like magic, in fact they are, at heart, instances of congruence arithmetic - exactly as above. After one has learned congruence arithmetic the problem can be easily transformed into the triviality $\ (27/8)^n\equiv\, 1^n\equiv 1\ $ since $\ 27\equiv 8\pmod{19 }.$

See also this answer on fractions in modular (congruence) arithmetic.