$7\mid 2\cdot8^n+3\cdot15^n+2$ is divisible by 7?

Question

I tryed a lot of ways to prove that and I can't.

My formula is:

$$ 2\cdot8^n+3\cdot15^n+2 $$

And I need to prove if is divisible by 7. Recently I got:

$$ 2\cdot8^1+3\cdot15^1+2 $$ $$ 63 $$

And with K+1 is:

$$ 2\cdot8^{k+1}+3\cdot15^{k+1}+2 $$ $$ \text{OR} $$ $$ 2^{3k+4}+3^{K+2}\cdot5^{k+1}+2 $$

But i can't find a solution... /:

Answer 1

$$ 2\cdot8^n+3\cdot15^n+2 $$ By Hyphotesis is divisible by $7$.

Then you need to prove that $$ 2\cdot8^{n+1}+3\cdot15^{n+1}+2 $$ is divisible by $7$

Substract the two expressions: $$ 2\cdot8^{n+1}-2\cdot8^{n}+3\cdot15^{n+1}-3\cdot15^{n+1}$$ $$ 2\cdot8^{n}\left(8-1\right)+3\cdot15^{n+1}\left(15-1\right)$$ $$ 2\cdot8^{n}\left(7\right)+3\cdot15^{n+1}\left(14\right)$$ Which is clearly divisible by $7$, then if $a-b$ and $b$ are divisible by $7$ then $a$ is divisible by $7$.

Answer 2

Hint: $$2\cdot8^{k+1}+3\cdot15^{k+1}+2 = \\ 2\cdot 8 \cdot 8^{k}+3\cdot 15 \cdot 15^{k}+2 = \\ (2\cdot8^{k}+3\cdot15^{k}+2)+(2\cdot 7 \cdot 8^{k} + 3\cdot 14 \cdot 15^{k}).$$

Answer 3

$2*8^n + 3*15^n + 2 = 2*(7+1)^n + 3*(14+1)^n + 2$, then $2 + 3 + 2 = 7$

Answer 4

A modular arithmetic solution is much faster. $2 \cdot 8^n+3 \cdot 15^n+2 \equiv 2\cdot 3 \cdot(1)^n+3 \equiv 2+3+2 \equiv 0$.

Equivalently, consider the binomial expansion $2 \cdot (7+1)^n + 3 \cdot (14+1)^n + 2$ and by Lucas's Theorem, we are done.

Answer 5

Note that (for integers $x$ and $k$) $7 \mid x + 7k$ implies $7 \mid x$. Since

$$8^n = (1+7)^n = \sum_{i=0}^n {n \choose i}7^i = 7\left(\sum_{i=1}^n {n \choose i}7^{i-1}\right) + 1 = 7k+1,$$

and similarly $15^n = 14k+1$, the equation is equivalent to

$$7 \mid 2 \cdot (7k + 1) + 3 \cdot (14k + 1) + 2$$

or

$$7 \mid 7 \cdot (8k) + 7$$

which is trivially true.

(In fact, this is just a roundabout way of saying that $8^n \equiv 15^n \equiv 1 \mod 7$.)

Answer 6

Another neat thing to know is that if $T_n=a\alpha^n+b\beta^n$ then $T_{n+2}=(\alpha+\beta)T_{n+1}-\alpha\beta T_n$ or $T_{n+2}-(\alpha+\beta)T_{n+1}+\alpha\beta T_n=0$

It is easy to see that if $U_n, V_n$ are solutions of the recurrence then $aU_n+bV_n$ is a solution too. Also that if we know $T_0, T_1$ these determine every value. It is also easy to check that $U_n=\alpha^n$ and $V_n=\beta^n$ are solutions. If $\alpha \neq \beta$ then we have $$T_0=a+b, T_1=a\alpha+b\beta$$ so that $$a=\frac{T_0\beta-T_1}{\beta-\alpha}, b=\frac{T_0\alpha-T_1}{\alpha-\beta}$$

Here, if we set $T_n=2\cdot 8^n +3\cdot 15^n$ and $S_n=T_n+2$ we have $S_{n+1}-S_n=T_{n+1}-T_n$

And we know that $$T_{n+2}=23T_{n+1}-120T_n$$

so that $T_{n+2}-T_{n+1}=22(T_{n+1}-T_n)-98T_n$

Finally we see that if $T_{n+1}-T_n$ is divisible by $7$ so is $T_{n+2}-T_{n+1}$, and the same is true for $S_n$

Reducing to a linear recurrence gets rid of the powers. The linearity of the recurrence makes it more obvious why divisibility persists. This is not necessarily a recommended method of solution, but rather an insight into what is going on.

Answer 7

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ $$ 2 \times 8^n + 3 \times 15^n =5 + 2\pars{8^n - 1} + 3\pars{15^n - 1} $$

$$ \pars{7\mu + 1}^{n} - 1 = 7\sum_{k = 1}^{n}{n \choose k}7^{k - 1}\mu^{k} \quad\imp\quad 7\ |\ \bracks{\pars{7\mu + 1}^{n} - 1} $$ With $\mu = 1,2$ we'll have $\ds{7\ |\ \pars{8^{n} - 1}}$ and $\ds{7\ |\ \pars{15^{n} - 1}}$ are $\color{#c00000}{\large true}$.

Then, $$\color{#00f}{\large% \pars{2 \times 8^n + 3 \times 15^n} \mod 7 = 5} $$