Is there a better way to prove this mathematical statement by induction?

[Random Variable]

I'm not even sure that my way is correct.

2^n + 3^n = 5^n (mod 6) for n >= 1 (n being an integer)

1) when n=1, 2+3 = 5 (mod 6), which is true since 6 divides 0

2) assume 2^k +3^k = 5^k (mod 6) is true for some k>1 (k being an integer)

3) show 2^(k+1) + 3^(k+1) = 5^(k+1) (mod 6)

(2 + 3)(2^k + 3^k) = (5)5^k (mod 6)

2^(k+1) + 2(3^k) + 3(2^k) + 3^(k+1) = 5^(k+1) (mod 6)

2^(k+1) + 3^(k+1) = -2(3^k) - 3(2^k) +5^(k+1) (mod 6)

2^(k+1) +3^(k+1) = 5^(k+1) (mod 6)

 

[esun]

What I would do is at this step:

2^(k+1) + 2(3^k) + 3(2^k) + 3^(k+1) = 5^(k+1) (mod 6)

Take out an extra 3 from the second term and a 2 from the third term like so:

2^(k+1) + 2*3(3^(k-1)) + 3*2(2^(k-1)) + 3^(k+1) = 5^(k+1) (mod 6)

2^(k+1) + 6(3^(k-1)) + 6(2^(k-1)) + 3^(k+1) = 5^(k+1) (mod 6)

Then it is more clear that those two terms are 0 mod 6 (you could even write that explicitly in words). Other than that looks fine.

 

[Random Variable]

Originally posted by: esun
What I would do is at this step:

2^(k+1) + 2(3^k) + 3(2^k) + 3^(k+1) = 5^(k+1) (mod 6)

Take out an extra 3 from the second term and a 2 from the third term like so:

2^(k+1) + 2*3(3^(k-1)) + 3*2(2^(k-1)) + 3^(k+1) = 5^(k+1) (mod 6)

2^(k+1) + 6(3^(k-1)) + 6(2^(k-1)) + 3^(k+1) = 5^(k+1) (mod 6)

Then it is more clear that those two terms are 0 mod 6 (you could even write that explicitly in words). Other than that looks fine.

That's quite clever. Thanks.

 

[speg]

I just woke up so maybe my brain hasn't but how do you go from:
2^(k+1) + 3^(k+1) to (2+3)(2^k + 3^k)?

 

[halik]

Hahaha welcome to the wonderfull world of useless computer science. Doing these proofs and later on language proofs (NP-Complete, NP-hard etc) will be of virtually no use to you in your professional life. However, your school has a staff of about 20 60year old tenured professors that can only do the above, so you have to learn all this pointless crap. (that's the explanation I've got from one of my real CS profs)

It amuses me that we still have fresh CS-graduates that can prove why an imaginary language is NP-complete, yet you'll get blank stares when you ask them about MVC or polymorphism.

 

[Random Variable]

Originally posted by: speg
I just woke up so maybe my brain hasn't but how do you go from:
2^(k+1) + 3^(k+1) to (2+3)(2^k + 3^k)?

I didn't. The first line of step 3 is just what I want to eventually show.

 

[ngvepforever2]

Originally posted by: halik
Hahaha welcome to the wonderfull world of useless computer science. Doing these proofs and later on language proofs (NP-Complete, NP-hard etc) will be of virtually no use to you in your professional life. However, your school has a staff of about 20 60year old tenured professors that can only do the above, so you have to learn all this pointless crap. (that's the explanation I've got from one of my real CS profs)

It amuses me that we still have fresh CS-graduates that can prove why an imaginary language is NP-complete, yet you'll get blank stares when you ask them about MVC or polymorphism.

Even though I get your point and I partially agree with you, I believe all this pointless "crap" should very interesting to do for a CS major. For me, at least, it helps me to develop my problem solving skills and understand the logic behind all the programs I write. Although it is ridicoulus to have a fresh CS grad not knowing what polymorphism is (mainly because this is supposed to be taught during your freshman year), I believe that if that same fresh CS graduate can understand and analyze complex algorithms, he/she should be able to pick up MVC rather quickly. Moreover, NP-Complete problems are fun to analyze and they are indeed used in the real world for certain applications.

<--CS Major, works in the corporate world btw...

Regards

ng

 

[halik]

Originally posted by: ngvepforever2

Originally posted by: halik
Hahaha welcome to the wonderfull world of useless computer science. Doing these proofs and later on language proofs (NP-Complete, NP-hard etc) will be of virtually no use to you in your professional life. However, your school has a staff of about 20 60year old tenured professors that can only do the above, so you have to learn all this pointless crap. (that's the explanation I've got from one of my real CS profs)

It amuses me that we still have fresh CS-graduates that can prove why an imaginary language is NP-complete, yet you'll get blank stares when you ask them about MVC or polymorphism.

Even though I get your point and I partially agree with you, I believe all this pointless "crap" should very interesting to do for a CS major. For me, at least, it helps me to develop my problem solving skills and understand the logic behind all the programs I write. Although it is ridicoulus to have a fresh CS grad not knowing what polymorphism is (mainly because this is supposed to be taught during your freshman year), I believe that if that same fresh CS graduate can understand and analyze complex algorithms, he/she should be able to pick up MVC rather quickly. Moreover, NP-Complete problems are fun to analyze and they are indeed used in the real world for certain applications.

<--CS Major, works in the corporate world btw...

Regards

ng

There's a big big difference between knowing the concepts of P, NP, halting problem etc. and knowing how to prove that this made-up scenario is NP. The important stuff from the class I took on the subject could be summarized over a weekend seminar.

I can guarantee you that you will never do any sorts of proofs in real world. Also, if you need to take that class to LEARN problem solving, you shouldn't be in CS to begin with.

 

[MAW1082]

Yeah what are you going to do, go around proving some random mathematical stuff to people for money?

Dear Sir or Madam,

I will come to your house and prove Maxwell's equations using ony simple algebraic proofs in three hours or less for 19.95 plus tax.

MAW