2

Here's what I did:

Base Case: $n = 1$, $2^3*5^3+3^3*2^3$ = $1216$ = $19(64)$

Induction Hypothesis (IH): $a_k=2^{k+2}\cdot 5^{2k+1}+3^{k+2}\cdot 2^{2k+1}$ for some $k\:\in \mathbb{N}$.

Inductive Step: $a_{k+1}=2^{\left(k+1\right)+2}\cdot \:5^{2\left(k+1\right)+1}+3^{\left(k+1\right)+2}\cdot \:2^{2\left(k+1\right)+1}$

$a_{k+1}=2^{\left(k+2\right)}\cdot 2\cdot \:5^{2k+1}\cdot 5^2+3^{k+2}\cdot 3\cdot \:2^{2k+1}\cdot 2^2$

$a_{k+1}=2^{k+2}\:\cdot 5^{2k+1}\cdot 50+3^{k+2}\cdot 2^{2k+1}\cdot 12$

How do I prove that the latter statement is divisible by 19?

(I've tried to set up the equation in a way where I know that $2^{k+2}\:\cdot 5^{2k+1}$ and $3^{k+2}\cdot 2^{2k+1}$ is divisible by 19. I'm not sure about the 50 and the 12.)

someman112
  • 409

1 Answers1

3

You're almost there! Hint for the finish: $$ 2^{k+2}\cdot 5^{2k+1}\cdot 50+3^{k+2}\cdot 2^{2k+1}\cdot 12\\ = 12\left(2^{k+2}\cdot 5^{2k+1}+3^{k+2}\cdot 2^{2k+1}\right) + 38\left(2^{k+2}\cdot 5^{2k+1}\right) $$

Arthur
  • 199,419
  • Just curious, is there a direct proof strategy for this claim? – Alan Abraham Dec 08 '21 at 22:52
  • 2
    @AlanAbraham Rewrite $a_n = 20 \cdot 50^n + 18 \cdot 12^n$. Modulo $19$, this becomes $1 \cdot 12^n + (-1) \cdot 12^n = 0$. – Theo Bendit Dec 08 '21 at 23:04
  • I get that the latter part of the equation is divisible by 19 because 19(2) = 38. Still not sure about the first part... – someman112 Dec 08 '21 at 23:13
  • @Yaya123 This is an induction proof. What was the induction hypothesis? – Arthur Dec 08 '21 at 23:18
  • @AlanAbraham Use the induction hypothesis as much as possible until the expression becomes strictly simpler. Then look at what you have left. – Arthur Dec 08 '21 at 23:20
  • By IH, $a_k=2^{k+2}\cdot 5^{2k+1}+3^{k+2}\cdot 2^{2k+1}$ for some $k:\in \mathbb{N}$ is divisible by 19 hence the first part is also divisible by 19 – someman112 Dec 08 '21 at 23:22
  • @Arthur I was just wondering since I had seen a similar problem and was wondering if there was any reason why it was intuitively true. – Alan Abraham Dec 08 '21 at 23:33
  • @AlanAbraham You mean something other than an induction proof like this? – Arthur Dec 09 '21 at 08:50