Prove that $3\cdot 5^{2n+1} +2^{3n+1}$ is divisible by $17$ for all $n ∈ \mathbb{N}$

Question

Use mathematical induction to prove that $3\cdot 5^{2n+1} +2^{3n+1}$ is divisible by $17$ for all $n ∈ \mathbb{N}$.

I've tried to do it as follow.

If $n = 1$ then $392/17 = 23$. Assume it is true when $n = p$. Therefore $3\cdot 5^{2p+1} +2^{3p+1} = 17k $ where $k ∈ \mathbb{N} $. Consider now $n=p+1$. Then \begin{align} &3\cdot 5^{2(p+1)+1} +2^{3(p+1)+1}=\\ &3\cdot 5^{2p+1+2} + 2^{3p+1+3}=\\ &3\cdot5^{2p+1}\cdot 5^{2} + 2^{3p+1}\cdot 2^{3}. \end{align} I reached a dead end from here. If someone could help me in the direction of the next step it would be really helpful. Thanks in advance.

Answer 1

Having shown that $$3\cdot5^{2p+1}+2^{3p+1}=17k$$ we have (continuing from the last line) $$3\cdot5^{2p+1}5^{2}+2^{3p+1}2^{3}=17(3\cdot5^{2p+1})+8(3\cdot5^{2p+1}+2^{3p+1})=17(3\cdot5^{2p+1}+8k)$$ so the next expression is also divisible by 17, as required.

Answer 2

Step $n+1:$

$3(5^2)5^{2p+1}+(2^3)2^{3p+1}=$

$3(17+8)5^{2p+1} +8 \cdot 2^{3p+1}=$

$8[3 \cdot 5^{2p+1}+2^{3p+1}]+ 17\cdot 3 \cdot 5^{2p+1}.$

The first term in the above sum is divisible by $17$ (hypothesis), the second term is a multiple of $17$.

Answer 3

I'll start with the inductive step

$$3\cdot5^{2(n+1)+1}+2^{3(n+1)+1}$$

$$3\cdot5^{2n+1+2}+2^{3n+1+3}$$

$$3\cdot25\cdot5^{2(n+1)}+8\cdot2^{3n+1}$$

We know that $$3\cdot5^{2n+1}+2^{3n+1}=17k$$

Therefore $$3\cdot5^{2n+1}=17k-2^{3n+1}$$

Plug this in: $$25\cdot(17k-2^{3n+1})+8\cdot2^{3n+1}$$

$$425k\cdot-25\cdot2^{3n+1}+8\cdot2^{3n+1}$$

$$425k\cdot-17\cdot2^{3n+1}$$

$$17(25-2^{3n+1})$$

Answer 4

Here are two alternative routes.

Using the binomial theorem: $$ 3\cdot 5^{2n+1} +2^{3n+1} = 15\cdot 25^{n} +2\cdot 8^{n} = 15\cdot (17+8)^{n} +2\cdot 8^{n}\\ = 15\cdot (17a+8^{n}) +2\cdot 8^{n} = 17b+15\cdot 8^{n} +2\cdot 8^{n} = 17b+17\cdot 8^{n} $$

Using recurrences:

Let $ x_n=3\cdot 5^{2n+1} +2^{3n+1} $, Since, as above, $ x_n= 15\cdot 25^{n} +2\cdot 8^{n} $, we have the recurrence $x_{n}=33x_{n-1}-200x_{n-2}$, for $n\ge 2$ (*). The result follows by induction because $x_0$ and $x_1$ are multiples of $17$.

(*) In general, if $x_n=a\alpha^{n} +b\beta^{n}$, then $x_{n}=(\alpha+\beta)x_{n-1}-(\alpha\beta)x_{n-2}$, for $n\ge 2$. This follows because $\alpha$ and $\beta$ are the roots of the quadratic $(x-\alpha)(x-\beta)=x^2-(\alpha+\beta)x+(\alpha\beta)$.

Answer 5

Conceptually the inductive step scales by $\,\color{#c00}{5^{\large 2} \equiv\, 2^{\large 3}}\pmod{\!17}.\,$ If you don't know congruences we can preserve this arithmetical essence by using a divisibility (vs. congruence) product rule where we used standard notation $\ m\mid n\ $ means $\,m\,$ divides $\,n.\,$

$$\qquad\ \ \begin {align} &17\mid\ \ \ \color{#c00}{5^{\large 2}\quad\ \ -\quad\ \ 2^{\large 3}}\\ &17\mid\ a\ \ \ 5^{\large 2n+1} -\ b\ \ \ \,2^{\large 3n+1}\qquad\ P(n)\\ \Rightarrow\ \ &17\mid a \color{#c00}{5^{\large 2}} 5^{\large 2n+1}\! -\,\ b \color{#c00}{2^{\large3}} 2^{\large 3n+1}\qquad P(n\!+\!1) \end{align} $$

$\begin{align}{\bf Divisibility\ Product\ Rule}\ \ \ \ &m\mid\ a\ -\ b\qquad {\rm i.e.}\quad \ a\,\equiv\, b\\ &m\mid \ \ A\: -\: B\qquad\qquad \ A\,\equiv\, B\\ \Rightarrow\ \ &\color{}{m\mid aA - bB}\quad \Rightarrow\quad aA\equiv bB\!\pmod{\!m}\\[.2em] {\bf Proof}\,\ \ m\mid (\color{#0a0}{a\!-\!b})A + b(\color{#0a0}{A\!-\!B}) &\,=\, aA-bB\ \ \text{by $\,m\,$ divides $\rm\color{#0a0}{green}$ terms by hypothesis.}\end{align}$

You can find further discussion in many prior posts.