• Support PF! Buy your school textbooks, materials and every day products Here!

Proof by Induction

  • Thread starter kathrynag
  • Start date
  • #1
598
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
 

Answers and Replies

  • #2
598
0
2*7*7^k+3*5*5^k-5
[2*7^k+3*5^k-5]+7*7^k+5*5^k
 
  • #3
12
0
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.
 
  • #4
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,305
998
2*7*7^k+3*5*5^k-5
[2*7^k+3*5^k-5]+7*7^k+5*5^k
Hi Kathryn.

[tex]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[/tex]
     [tex]=\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[/tex]

     [tex]=\left(2\cdot 7^k+3\cdot 5^k-5\right)+12\left( 7^k+ 5^k\right)[/tex]

Can you take it from here?
 
  • #5
598
0
Yep, I can see both values are divisible by 24. Thanks!
 
  • #6
14
0
Hi Kathryn.

[tex]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[/tex]
     [tex]=\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[/tex]

     [tex]=\left(2\cdot 7^k+3\cdot 5^k-5\right)+12\left( 7^k+ 5^k\right)[/tex]

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?
 
  • #7
14
0
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?
 
  • #8
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,305
998
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:
  • #9
14
0
(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.
 

Related Threads on Proof by Induction

  • Last Post
Replies
6
Views
748
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
606
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
2
Views
891
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
9
Views
1K
Top