How to Use Proof by Induction for 24|2*7^n+3*5^n-5

[kathrynag]

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

 

[kathrynag]

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

 

[mathstew]

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]

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?

 

[kathrynag]

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

 

[barylwires]

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?

 

[barylwires]

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]

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.

 

[barylwires]

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