11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – quid Dec 10 '14 at 21:54
  • $\begingroup$ Unfortunately yes. The question is written this way. $\endgroup$ – amundi12 Dec 10 '14 at 21:55
  • $\begingroup$ Ehh. Do what @quid said and prove those more basic facts by induction. $\endgroup$ – djechlin Dec 11 '14 at 1:12
16
$\begingroup$

Keep going!

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

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

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

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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