Prove by induction that an expression is divisible by 11

Question

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?

Answer 1

Keep going!

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

Answer 2

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})$

Answer 3

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})$$

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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.

Answer 8

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

Answer 9

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.