4
$\begingroup$

I want to prove that $2^{n+2} +3^{2n+1}$ is divisible by $7$ for all $n \in \mathbb{N}$ using proof by induction.

Attempt

Prove true for $n = 1$

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

35 is divisible by 7 so true for $n =1$

Induction step: Assume true for $n = k$ and prove true for $n = k+1$

$n = k$

$2^{k+2} + 3^{2k +1} = 2^k \cdot 2^2 + 3^{2k} \cdot 3^1 = (4) 2^k + (3) 3^{2k}$

$n = k+1$

$2^{k+3} +3^{2k+3} = (8) 2^k + (27) 3^{2k}$

Thoughts:

I know I need to use the expression for $n = k$ to prove that it is true for $n = k+1$ but I am not sure where to start. I think that using modular arithmetic would be too complex. Any ideas would be greatly appreciated!

Update

Thanks for all of the useful answers/suggestions. I understand the approach to take now!

$\endgroup$
  • 1
    $\begingroup$ If $u_n=Aa^n+Bb^n$ it is easy to check that $u_n-(a+b)u_{n-1}+abu_{n-2}=0$ and therefore divisibility persists once it is established. This isn't very different from the methods you will see below, but it does provide a quick way of getting the right coefficients. Here $a=2, b=3^2=9$ are required. $\endgroup$ – Mark Bennet Sep 13 '17 at 10:28
  • 1
    $\begingroup$ Better use the LaTeX symbol \cdot instead of a period (end-of-sentence mark) to denote multiplication. $\endgroup$ – CiaPan Sep 13 '17 at 10:36
10
$\begingroup$

\begin{eqnarray*} 2^{k+3}+3^{2k+3} =(9-7)2^{k+2} +9 \times 3^{2k+1}= 9(\color{blue}{2^{k+2}+3^{2k+1}})-\color{blue}{7} \times2^{k+2} \end{eqnarray*}

$\endgroup$
4
$\begingroup$

Hint: Write the equation for $n=k$ equal to $7(c)$ where $c$ is some constant. Now, look hard at the equation where $n=k+1$.

$\endgroup$
3
$\begingroup$

You're almost there. What is $2^{k+3} + 3^{2k + 3} - 2(2^{k+2} +3^{2k+1})$, according to your rewritings?

$\endgroup$
2
$\begingroup$

HINT.-$x+y\equiv0\pmod7$ this implies $2x+9y\equiv2x+2y\equiv2(x+y)\equiv0\pmod7$

$\endgroup$
1
$\begingroup$

You mentioned that modular arithmetic would be to complex, but that's the approach I'd take and I actually found it fairly straightforward, so here's an alternative solution. We're working modulo 7, so there can't be any more than 7 different answers for $k^n$ that we care about. That's small enough for an exhaustive search;

\begin{align} n=0 \quad\quad& 2^{2} \cong 4 \quad\quad& 3^{1} \cong 3 \quad\quad& 4+3 \cong 0 \\ n=1 \quad\quad& 2^{3} \cong 1 \quad\quad& 3^{3} \cong 6 \quad\quad& 1+6 \cong 0 \\ n=2 \quad\quad& 2^{4} \cong 2 \quad\quad& 3^{5} \cong 5 \quad\quad& 2+5 \cong 0 \\ n=3 \quad\quad& 2^{5} \cong 4 \quad\quad& 3^{7} \cong 3 \quad\quad \end{align}

And lucky us, we can stop early! Our residues for $n=3$ are the same as for $n=0$, and we generate each new row by multiplying both of the values in the two middle columns by 2 (since $3^2 \cong 2$).

So the pairs of residues can only ever by $(4,3), (1,6)$ or $(2,5)$. Adding any of these pairs yields a multiple of 7, QED.

$\endgroup$
  • $\begingroup$ Thanks for that explanation! $\endgroup$ – Sjoseph Sep 13 '17 at 15:11
1
$\begingroup$

Yet another view:

Take your $n=k$ version and double it. Then add $21(3^{2k})$ and you have your $k+1$ expression. Both things you're adding are divisible by $7$

$\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.