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

  • Thread starter Thread starter kathrynag
  • Start date Start date
  • Tags Tags
    Induction Proof
kathrynag
Messages
595
Reaction score
0
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
 
Physics news on Phys.org
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.
 
kathrynag said:
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!
 
SammyS said:
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 said:
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?
 
barylwires said:
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:
SammyS said:
(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.
 
Back
Top