4
$\begingroup$

How do I do this? I've tried using logarithms, factoring, but nothing seems to work.

$\endgroup$
4
$\begingroup$

Hint for the inductive step after the basis case:

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

$$=2\left(3^{3n+1}+2^{n+1}\right)+25\cdot3^{3n+1}$$

$\endgroup$
3
$\begingroup$

You can use modular arithmetic :

Suppose $3^{3n+1}+2^{n+1}$ is divisible by 5, then

$3^{3n+1} \equiv -2^{n+1}[5]$

so you have

$$3^{3(n+1)+1}+2^{n+1+1} \equiv 27 \times 3^{3n+1}+2 \times2^{n+1} [5]$$

$$3^{3(n+1)+1}+2^{n+1+1} \equiv 27 \left( -2^{n+1} \right) +2 \times2^{n+1} [5]$$

$$3^{3(n+1)+1}+2^{n+1+1} \equiv -25 \times2^{n+1} [5]$$

$$3^{3(n+1)+1}+2^{n+1+1} \equiv 0 [5]$$

$\endgroup$
2
$\begingroup$

HINT:

If $f(n)=3^{3n+1}+2^{n+1}$

$$f(m+1)-a\cdot f(m)=3^{3m+1}(3^3-a)+2^{m+1}(2-a)$$

If we set

$3^3-a=0\iff a=3^3\implies f(m+1)-3^3f(m)=\cdots\equiv0\pmod5$

or

$2-a=0\iff a=2\implies f(m+1)-2f(m)=\cdots\equiv0\pmod5$

$\implies5|f(m+1)\iff5|f(m)$


Non-inductive methods:

$(1)$Binomial Expansion:

$3^3=25+2\implies3^{3n+1}+2^{n+1}=2^{n+1}+3(2+25)^n$

$=2^{n+1}+3[2^n+\sum_{r=1}^n\binom nr2^{n-1}25^r]=2^n(2+3)+($ a multiple of $25)$

$(2)$Modular Arithmetic

$3^3\equiv2\pmod5\implies3^{3n+1}=3(3^3)^n\equiv3\cdot2^n\pmod5$

$\endgroup$
2
$\begingroup$

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

$3^{3\cdot1+1}+2^{1+1}=85$

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

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

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

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

$3^{3n+4}+2^{n+2}=$

$27(3^{3n+1})+2(2^{n+1})=$

$27(\color{red}{3^{3n+1}+2^{n+1}})-25(2^{n+1})=$

$27(\color{red}{5k})-25(2^{n+1})=$

$5(27k-5(2^{n+1}))$


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

$\endgroup$
1
$\begingroup$

Other users have already outlined the proof by induction, but I think a direct proof is interesting as well.

By Fermat's little theorem (or by inspection), we know that

$$3^4 \equiv 2^4 \equiv 1 \pmod{5}$$

This means that powers of $3$, modulo $5$, are determined by the exponents remainder when divided by $4$.

$$3^{3n+1} \equiv \begin{cases}3 \pmod{5} &\mbox{if }\,\, n \equiv 0 \pmod{4}\\ 1 \pmod{5} &\mbox{if }\,\, n \equiv 1 \pmod{4}\\ 2 \pmod{5} &\mbox{if }\,\, n \equiv 2 \pmod{4}\\ 4 \pmod{5} &\mbox{if }\,\, n \equiv 3 \pmod{4}\\ \end{cases}$$

$$2^{n+1} \equiv \begin{cases}2 \pmod{5} &\mbox{if }\,\, n \equiv 0 \pmod{4}\\ 4 \pmod{5} &\mbox{if }\,\, n \equiv 1 \pmod{4}\\ 3 \pmod{5} &\mbox{if }\,\, n \equiv 2 \pmod{4}\\ 1 \pmod{5} &\mbox{if }\,\, n \equiv 3 \pmod{4}\\ \end{cases}$$

For each possible residue for $n$ modulo $4$, the sum is $0$ modulo $5$.

$\endgroup$
1
$\begingroup$

Divisibility by $5$ is unaffected if we multiply the given expression by $9=3^2$. So let's consider $$ 3^{3n+3}+9\times2^{n+1}\equiv(3^3)^{n+1}-2^{n+1}=27^{n+1}-2^{n+1}\equiv 2^{n+1}-2^{n+1}=0\pmod{5}. $$

$\endgroup$
1
$\begingroup$

Note $\ 3\cdot 27^n + 2\cdot 2^n = 3(27^n-2^n) + 5\cdot 2^n\,$ so it suffices to prove $\,5\mid 27^n-2^n.\,$

Below are few ways, using conceptual lemmas, all which have easy (inductive) proofs.

$(1)\ \ \ a-b\mid a^n-b^n\,$ so $\,25\mid 27^n-2^n.\,$

$(2)\ \ \ (2+25)^n-2^n = 25k\,$ for $\,k\in \Bbb Z\,$ by the Binomial Theorem.

$(2)\ \ \ {\rm mod}\ 5\!:\ 27\equiv 2\,\Rightarrow\, 27^n\equiv 2^n\,$ so $\,3\cdot 27^n+2\cdot 2^n\equiv 5\cdot 2^n\equiv 0.\,$ by Congruence Rules. Most of the other proofs are essentially the same as this, but without the congruence language. See here where I explain how such proofs essentially unwind a proof of the Congruence Product Rule.

$\endgroup$
1
$\begingroup$

Note that the expression is $x_n=3\cdot 27^n+2\cdot 2^n$.

It is a fact that any $y_n=A\cdot a^n+B\cdot b^n$ satisfies the recurrence relation (which can be verified by direct computation) $$y_{n+2}=(a+b)\cdot y_{n+1}-ab\cdot y_n$$

From this we deduce that if $p\mid y_n$ and $p\mid y_{n+1}$ then $p\mid y_{n+2}$ This explains why divisibility, once established for two consecutive elements, persists for all elements in a wide range of these expressions, which often crop up as examples.

Here $x_{n+2}=29x_{n+1}-54x_n$

This method uses two base cases, of course, so isn't pure induction - but it explains what it is that makes the induction work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.