1

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

J. W. Tanner
  • 60,406
Samuele B.
  • 761

3 Answers3

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$.

J. W. Tanner
  • 60,406
  • Actually no, I just started yesterday with algebra and I don't really have much knowledge yet. I see that, if I can prove that $16^{k-1}\cdot16\cdot15$ is divisible by $24$, then the whole RHS is, since the other factor is $16^k-16$, which is divisible by $24$ per hypothesis. I can see that $16\cdot15 = 2^4\cdot5\cdot3$, and $24$ has the factors $2^3, 3$. Isn't a factor of $5$ missing in order for them to be divisible? – Samuele B. Jan 29 '20 at 13:57
  • 1
    $16\cdot15=8\cdot2\cdot3\cdot5=24\cdot10$, so $24$ divides $16\cdot15$ – J. W. Tanner Jan 29 '20 at 14:01
  • What about the remaining $16^{k-1}$ in the equation? Does it not matter because $16$ to any power is still going to have the same prime factors so it's still divisible? – Samuele B. Jan 29 '20 at 14:02
  • 1
    If $24$ divides $16\cdot15$ then $24$ divides $16^{k-1}\cdot16\cdot15$, as long as $k\ge1$ so $16^{k-1}$ is an integer – J. W. Tanner Jan 29 '20 at 14:07
  • Thank you for your quick and clear explanation. – Samuele B. Jan 29 '20 at 14:09
0

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)$

lab bhattacharjee
  • 274,582
0

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

lhf
  • 216,483