1

I need help solving this task, if anyone had a similar problem it would help me.

The task is:

Proof by mathematical induction:

$3\mid5^{n-1}+2^{n}$

I tried this:

$n=1:$

$5^0+2^1=1+2=3 \implies 3:3=1$

$n=k:$

$5^{k-1}+2^{k}=3a$

$n=k+1:$

$5^{k}+2^{k+1}=5^k+2^k\cdot 2$

And now, I don't know how to take advantage of the assumption $5^{k-1}+2^{k}=3a$.

Thanks in advance !

player3236
  • 16,413
LogicNotFound
  • 465
  • 2
  • 6
  • 1
    You can now substitute $2^k = 3a-5^{k-1}$. – player3236 Oct 13 '20 at 13:59
  • Alternatively note that $5^k+2^k\cdot 2 = 5^{k-1}\cdot 5 + 2^k\cdot 2 = 5^{k-1}\cdot 2 + 5^{k-1}\cdot 3 + 2^k\cdot 2$, that you can factor out an additional term and split it apart as desired. – JMoravitz Oct 13 '20 at 14:04
  • It is easy enough without induction. All you need to know is that: $5 = -1 (mod 3) $ and $2 = -1 (mod 3) $. Afterwards, notice that if $n$ is even, $n-1$ is odd or vice-versa. This is useful even for the induction. In the end you get $5\cdot5^{k-1} + 2\cdot2^k = -1\cdot5^{k-1} + (-1)\cdot2^k = - (5^{k-1} + 2^k) = -3a$ – Limsup Oct 13 '20 at 14:04
  • $5^k+2^k\cdot 2=2(5^{k-1}+2^k)+3(5^{k-1})$ – J. W. Tanner Oct 13 '20 at 15:00

2 Answers2

1

We have that by inductive hypothesis

$$3|(5^{k-1}+2^{k}) \iff 5^{k-1}+2^{k}=3h \iff 5^k=3\cdot 5h-5\cdot 2^k$$

then

$$5^{k}+2^{k+1} =3\cdot 5h-5\cdot 2^k+2^{k+1}=3\cdot 5h+2^k(-5+2)=3 \cdot(5h-2^k)$$

user
  • 154,566
0

You are almost there, if you notice that $2^k=3a-5^{k-1}$ then you have $5^k+2^{k+1}=5 ×5^{k-1}+6a-2× 5^{k-1}$=$3 ×5^{k-1}+6a$. The last one is divided by $3$ and we are done.

dmtri
  • 3,270