$$\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.
Best Answer
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$.