# Prove by induction: $2^{n+2} +3^{2n+1}$ is divisible by $7$ for all $n \in \mathbb{N}$

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!

• 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. – Mark Bennet Sep 13 '17 at 10:28
• Better use the LaTeX symbol \cdot instead of a period (end-of-sentence mark) to denote multiplication. – CiaPan Sep 13 '17 at 10:36

\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*}

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

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

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

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;

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