Prove by induction that $\forall n \in \mathbb{N}, n\ge1, \text{ }24\text{ divides } 16^n-16 $

Question

$$\forall n \in \mathbb{N}, n\ge1$$$$\text{ }24\text{ divides } 16^n-16 $$

I'm making my first small steps in algebra and I started studying induction. I still have difficulties with proving statements by induction.

This is what I've tried to prove the above:

(i) Base case $$P(1) \equiv 24\text{ divides } 16^1 - 16 \equiv 24 \text{ divides } 0 \equiv \text{tt}$$(ii) Induction step $$\text{Assume that, for unspecified } k, 24 \text{ divides } 16^k - 16$$ $$\text{then } 24 \text{ divides } 16^{k+1}-16$$

We have that $$16^k-16 = 16(16^{k-1}-1)$$ hence $24$ divides that. Now we also have that $$16^{k+1}-16 = 16(16^k-1)$$

I don't know how to complete the proof though. What am I missing? What should I look for when making this kind of proofs? Thank you.

Answer 1

Hint:

$16^{k+1}-16=16^{k+1}-16^k+16^k-16$

$=16^k(16-1)+16^k-16=16^{k-1}\cdot16\cdot15+(16^k-16)$.

Can you show the right side is divisible by $24=8\cdot3$?

---

Also, it's easy to prove the result using modular arithmetic:

$3|16^n-16$ since $16\equiv1\pmod3$, and $8|16^n-16$ since $16\equiv0\pmod8$.

Answer 2

If $f(m)=16^m-16$

$$f(n+1)-16f(n)=\cdots=16^2-16=16(16-1)$$

So, if integer $d$ where $d|16(16-1)$ divides $f(n),d$ will divide $f(n+1)$

Answer 3

Write $16^n=16+24a$ with $a \in \mathbb Z$. Then $16^{n+1}=16^2+24(16a)=16+24(16a+10)$.