Prove by Induction $19^{n}-4^{2n}$ is divisible by 3

Question

Assume $n=0$ for $19^{n}-4^{2n}$

Just going to do some simplification first: $19^{n}-4^{2n}\implies19^{n}-16^{n}$ and if $n=0$ then $19^{0}-16^{0}$ then it is zero which is obviously divisible by 3.

Now for the inductive hypothesis $19^{n}-16^{n}\mod{3}=0$

So now I show it for the case $n+1$ and one gets: $19^{n+1}-16^{n+1}\implies19^{n}\cdot19-16^{n}\cdot16$ but from here how do I show divisibility by 3?

Answer 1

Let $19^n-16^n=3k$ then $$19^{n+1}-16^{n+1}$$ $$=19^n\cdot19-16^n\cdot16$$ $$=(3k+16^n)19-16^n\cdot16$$ $$=57k+19\cdot16^n-16\cdot16^n$$ $$=57k+3\cdot16^n$$ $$=3\lambda$$

Answer 2

So you’re off to a good start. The next step is just to realize that $19-16=3$, which is the reason this is true at all.

So you have: $$19(19^n) - 16(16^n) = (16+3)19^n - 16(16^n) = 16(19^n - 16^n)+3(19^n)$$

Now from your induction assumption $(19^n - 16^n)$ is a multiple of 3, and $3(19^n)$ is clearly a multiple of 3. You’re adding two multiples of 3, the result is a multiple of 3