# Proof by Induction

Prove 24|2*7^n+3*5^n-5

I showed true for n=1:
2*7+3*5-5=14+15-5=24
Thus divisible by 24
Assume true for all k>=1. Need to prove true for n=k+1
Then 2*7^(k+1)+3*5^(k+1)-5=14*7^k+15*5^k-5
I get this far and now I get stuck simplifying enough to show it's true

## Answers and Replies

2*7*7^k+3*5*5^k-5
[2*7^k+3*5^k-5]+7*7^k+5*5^k

Instead of using induction try a simple congruence argument.

24 divides 2(7)^n + 3(5)^n - 5 iff 2(7)^n + 3(5)^n = 5 mod 24

Now if n is even this is true since 7^2 = 5^2 = 1 mod 24

If is n is odd the result is also immediate.

SammyS
Staff Emeritus
Homework Helper
Gold Member
2*7*7^k+3*5*5^k-5
[2*7^k+3*5^k-5]+7*7^k+5*5^k
Hi Kathryn.

$$2\cdot 7\cdot 7^k+3\cdot 5\cdot 5^k-5=2\cdot \left(1+6\right)\cdot 7^k+3\cdot \left(1+4\right)\cdot 5^k-5$$
$$=\left(2\cdot 7^k+3\cdot 5^k-5\right)+2\cdot \left(6\right)\cdot 7^k+3\cdot \left(4\right)\cdot 5^k$$

$$=\left(2\cdot 7^k+3\cdot 5^k-5\right)+12\left( 7^k+ 5^k\right)$$

Can you take it from here?

Yep, I can see both values are divisible by 24. Thanks!

Hi Kathryn.

$$2\cdot 7\cdot 7^k+3\cdot 5\cdot 5^k-5=2\cdot \left(1+6\right)\cdot 7^k+3\cdot \left(1+4\right)\cdot 5^k-5$$
$$=\left(2\cdot 7^k+3\cdot 5^k-5\right)+2\cdot \left(6\right)\cdot 7^k+3\cdot \left(4\right)\cdot 5^k$$

$$=\left(2\cdot 7^k+3\cdot 5^k-5\right)+12\left( 7^k+ 5^k\right)$$

Can you take it from here?

I see that 12(7^k + 5^k) is divisible by 24 when k=1, but why does that suffice for all k>1? Don't I have to prove that?

I see that 12(7^k + 5^k) is divisible by 24 when k=1, but why does that suffice for all k>1? Don't I have to prove that?

I mean, the left side is divisible by 24 by induction hypothesis. Why do I get the right side for free? Or, do I?

SammyS
Staff Emeritus
Homework Helper
Gold Member
I see that 12(7^k + 5^k) is divisible by 24 when k=1, but why does that suffice for all k>1? Don't I have to prove that?

[STRIKE](You're hitch-hiking on Kathryn's post.)[/STRIKE]

7^k is odd, so is 5^k. The sum of two ODDs is even, thus contains a factor of 2.

Prove it if you like, but a simple statement like that would usually suffice.

Last edited:
(You're hitch-hiking on Kathryn's post.)

7^k is odd, so is 5^k. The sum of two ODDs is even, thus contains a factor of 2.

Prove it if you like, but a simple statement like that would usually suffice.

That's beautiful! Thanks.