# Prove by induction that an expression is divisible by 11

Prove, by induction that $2^{3n-1}+5\cdot3^n$ is divisible by $11$ for any even number $n\in\Bbb N$.

I am rather confused by this question. This is my attempt so far:

For $n = 2$

$2^5 + 5\cdot 9 = 77$

$77/11 = 7$

We assume that there is a value $n = k$ such that $2^{3k-1} + 5\cdot 3^k$ is divisible by $11$.

We show that it is also divisible by $11$ when $n = k + 2$

$2^{3k+5} + 5\cdot 3^{k+2}$

$32\cdot 2^3k + 5\cdot 9 \cdot3^k$

$32\cdot 2^3k + 45\cdot 3^k$

$64\cdot 2^{3k-1} + 45\cdot 3^k$ (Making both polynomials the same as when $n = k$)

$(2^{3k-1} + 5\cdot 3^k) + (63\cdot 2^{3k-1} + 40\cdot 3^k)$

The first group of terms $(2^{3k-1} + 5\cdot 3^k)$ is divisible by $11$ because we have made an assumption that the term is divisible by $11$ when $n=k$. However, the second group is not divisible by $11$. Where did I go wrong?

• Do you have to show it by induction? If not you could use that $2^n$ and $3^n$ are periodic modulo 11 and just check over one period. – quid Dec 10 '14 at 21:54
• Unfortunately yes. The question is written this way. – amundi12 Dec 10 '14 at 21:55
• Ehh. Do what @quid said and prove those more basic facts by induction. – djechlin Dec 11 '14 at 1:12

Keep going!

$64\cdot 2^{3k-1} + 45\cdot 3^k = 9(2^{3k-1} + 5\cdot3^k) + 55\cdot2^{3k-1}$

• Oh, I totally did not see that. – amundi12 Dec 10 '14 at 21:59

hint: You may want to reconsider the way you split the terms at the end.

Note that $64(2^{3k - 1}) + 45(3^k) = 9(2^{3k - 1} + 5(3^k)) + 55(2^{3k - 1})$

• sorry. Didn't realize it was already answered. – NMEM Dec 10 '14 at 22:03

Hint note that: if $k$ is a even number then also the next number $k+2$ is even

$$2^{3(k+2)-1}+5\cdot3^{k+2}=2^{3k-1+6}+5\cdot3^{k+2}=64\cdot2^{3k-1}+9\cdot5\cdot3^{k}$$$$=55\cdot2^{3k-1}+9\cdot2^{3k-1}+9\cdot5\cdot3^{k}=55\cdot2^{3k-1}+9\cdot(2^{3k-1}+5\cdot3^{k})$$

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

• $\frac{2^{3\cdot2-1}+5\cdot3^1}{11}=7\in\mathbb{N}$

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

• $\frac{2^{3n-1}+5\cdot3^n}{11}=k\in\mathbb{N}$

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

• $\frac{2^{3(n+2)-1}+5\cdot3^{n+2}}{11}=\frac{2^{3n+5}+5\cdot3^{n+2}}{11}$

• $\frac{2^{3n+5}+5\cdot3^{n+2}}{11}=\frac{2^6\cdot2^{3n-1}+3^2\cdot5\cdot3^n}{11}$

• $\frac{2^6\cdot2^{3n-1}+3^2\cdot5\cdot3^n}{11}=\frac{64\cdot2^{3n-1}+9\cdot5\cdot3^n}{11}$

• $\frac{64\cdot2^{3n-1}+9\cdot5\cdot3^n}{11}=\frac{55\cdot2^{3n-1}+9\cdot2^{3n-1}+9\cdot5\cdot3^n}{11}$

• $\frac{55\cdot2^{3n-1}+9\cdot2^{3n-1}+9\cdot5\cdot3^n}{11}=\frac{55\cdot2^{3n-1}+9(2^{3n-1}+5\cdot3^n)}{11}$

• $\frac{55\cdot2^{3n-1}+9(2^{3n-1}+5\cdot3^n)}{11}=\frac{55\cdot2^{3n-1}+9\cdot11k}{11}$ assumption used here

• $\frac{55\cdot2^{3n-1}+9\cdot11k}{11}=\frac{11(5\cdot2^{3n-1}+9k)}{11}$

• $\frac{11(5\cdot2^{3n-1}+9k)}{11}=5\cdot2^{3n-1}+9k\in\mathbb{N}$

This is the same as proving that $2^{6n-1}+5\cdot3^{2n}$ is divisible by $11$ for all $n$. The case $n=1$ is obvious.

By induction hypothesis, you can assume $2^{6n-1}+5\cdot3^{2n}=11k$, which can be written $$2^{6n-1}=11k-5\cdot3^{2n}$$ Now \begin{align} 2^{6(n+1)-1}+5\cdot3^{2(n+1)} &=2^6\cdot2^{6n-1}+45\cdot3^{2n}\\ &=2^6(11k-5\cdot3^{2n})+45\cdot3^{2n}\\ &=11\cdot 2^6k+3^{2n}(45-5\cdot64) \end{align} and you're done because $45-5\cdot64=-275=-11\cdot16$.

This might be irrelevant but it is equal to $2^{6n-1}+5 \cdot 9^n=2^{6n-6} \cdot 2^5+5\cdot 9^n$

Now since $2^6=64 \equiv -2 (mod 11)$, and $9^n \equiv -2(mod 11)$, the whole expression is equivalent to $(-2)^{n-1} \cdot 32+5 \cdot (-2)^n (mod 11) \equiv (-2)^n \cdot -16+5 \cdot (-2)^n (mod 11) \equiv 11 \cdot (-2)^n (mod 11)$, which is divisible by 11.

\begin{align}2^{3}\equiv -3\pmod {11} & \implies 3^n\equiv 2^{3n}\pmod {11} \ \color{blue}{(\text{since}\ n\ \text{is even})}\\& \implies 2^{3n-1}+5\cdot 3^n\equiv 2^{3n-1}+5\cdot 2^{3n}\pmod {11}\\&\implies2^{3n-1}+5\cdot 3^n\equiv 2^{3n-1}(1+5\cdot 2)\pmod {11}\\&\implies 2^{3n-1}+5\cdot 3^n\equiv 0\pmod {11}\end{align}

Hint $\$ Times $2$ it is equivalent to $\,{\rm mod}\ 11\!:\ 8^n - 3^n\equiv 0,\,$ i.e.$\ 3^n\equiv (-3)^n\equiv \color{#c00}{(-1)^n} 3^n.\,$ Thus it suffices to prove $\ n$ even $\,\Rightarrow\, \color{#c00}{(-1)^n}\equiv 1,\,$ which is straightforward (by induction or not).

Hint. Let $A_k = 2^{3k-1}+5\cdot 3^k = \frac{1}{2}\cdot 8^k+5\cdot 3^k$.
Once you prove that the sequence $\{A_k\}_{k\geq 1}$ fulfills the recurrence relation $$A_{k+2} = 11\cdot A_{k+1} -24\cdot A_k$$ you trivially have that $A_{k+2}\equiv -2\cdot A_k\pmod{11}$ holds.
$A_2=77\equiv 0\pmod{11}$ and the conclusion is straightforward.