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!
Best Answer
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).