Prove divisibility by induction $19\mid 5^{2n+1}2^{n+2}+3^{n+2}2^{2n+1}$

Question

Prove that $5^{2n+1}2^{n+2}+3^{n+2}2^{2n+1}=19k$ for all $n$ natural numbers. I have tried writing 19 as a sum of two numbers and then proving that the LHS is a sum of the form $Ax+By=(A+B)k$but I couldn't manage to set $x=y=k$.

Answer 1

First, show that this is true for $n=1$:

$5^{2+1}\cdot2^{1+2}+3^{1+2}\cdot2^{2+1}=19\cdot64$

Second, assume that this is true for $n$:

$5^{2n+1}\cdot2^{n+2}+3^{n+2}\cdot2^{2n+1}=19k$

Third, prove that this is true for $n+1$:

$5^{2(n+1)+1}\cdot2^{(n+1)+2}+3^{(n+1)+2}\cdot2^{2(n+1)+1}=$

$50\cdot(\color\red{5^{2n+1}\cdot2^{n+2}+3^{n+2}\cdot2^{2n+1}})-38\cdot3^{n+2}\cdot2^{2n+1}=$

$50\cdot\color\red{19k}-38\cdot3^{n+2}\cdot2^{2n+1}=$

$19\cdot50k-38\cdot3^{n+2}\cdot2^{2n+1}=$

$19\cdot50k-19\cdot3^{n+2}\cdot2^{2n+2}=$

$19\cdot(50k-3^{n+2}\cdot2^{2n+2})$

---

Please note that the assumption is used only in the part marked red.

Answer 2

Hint: For the inductive step, observe that

$5^{2n+3}\cdot 2^{n+3}+3^{n+3}\cdot 2^{2n+3}=50(5^{2n+1}\cdot 2^{n+2})+12(3^{n+2}\cdot2^{2n+1})$

Answer 3

We have $$f(n)=20\cdot50^n+18\cdot12^n$$

Things become easier to manage if we can eliminate $50^n$ or $12^n$

$$f(m+1)-12f(m)=20\cdot50^m(50-12)$$ which is divisible by $19$

$\implies$

$$19|f(m+1)\iff19|f(m)$$

Now establish the base case i.e., for $n=1$

---

If induction is not mandatory,

$$20\cdot50^n+18\cdot12^n\equiv50^n-12^n$$ which is divisble by $50-12$ using Why $a^n - b^n$ is divisible by $a-b$?

Answer 4

$$5^{2n+1} 2^{n+2} + 3^{n+2}2^{2n+1} = 20 \cdot 50^n + 18 \cdot 12^n = (19+1)(38+12)^n + (19-1) 12^n = 19k + 12^n -12^n$$ for all $n\geq 0$.

For a more general result: Suppose $a$, $b$ and $x\neq y$ are integers and $z_n = a \cdot x^n + b \cdot y^n$. Then $z_{n+2} = (x+y) z_{n+1} - xy z_{n}$ for all $n \geq 0$. Hence $z_n$ is divisible by a fixed nonzero integer $m$ for all $n$ if and only if $z_0$ and $z_1$ are divisible by $m$.

Answer 5

$\begin{align}{\rm Hint\!:\ multiplying}\ \ \ 5^{\large 2n+1} 2^{\large n+2} &\equiv - 3^{\large n+2} 2^{\large 2n+1}\!\!\!\!\pmod{\!19}\\ {\rm by}\quad\ \ 5^{\large 2}\cdot 2\quad\ \ \ &\equiv\quad\ \ 3\cdot 2^{\large 2}\ \ \ \ \pmod{\!19}\end{align}\ \ $ yields the inductive step