Proof by induction?

careless25 · 2012-05-21 14:19:33

Here is the question: http://pastebin.com/8yrJxMKE
I am sure this has to be proved by induction.
I am guessing my basis step would be, for n rocks where n = 2, then k*m = 1 = (n(n-1))/2 = 1.
induction hypothesis: basis step holds true for n >= 2

Now I am stuck, because k*m could break apart easily into many different possibilities and if i try to keep it such that k decreases and m is always 1, this doesnt take into account all the possibilities.

Can someone give me a little push in the right direction?

Thanks!

Last edited by careless25 (2012-05-21 14:21:31)

anonimnystefy · 2012-05-21 16:55:57

Hi careless25

Well if the su mof the first n numbers is.n(n+1)/2 then the sum of the.first n+1 elements is n(n+1)/2 + n+1 =(n^2+n+2n-2)/2=(n^2+3n+2)/2=(n+1)(n+2)/2

Qed

Oh and your formula is.not correct. It is n(n+1)/2 like I wrote up there.

Stefy

Last edited by anonimnystefy (2012-05-22 04:08:56)

careless25 · 2012-05-22 03:29:36

Thanks a lot, though the formula is n(n-1)/2 but i can account for that in my proof.

I need help with one more proof.

Prove that GCD(ab,c) = GCD(a,c) * GCD(b,c)

anonimnystefy · 2012-05-22 04:09:42

Am I imagining,or did you change your original question?

careless25 · 2012-05-22 04:49:04

No I need help with another question and its easier to continue in this thread than create another.

Prove GCD(ab,c) = GCD(a,c) * GCD(b,c)

anonimnystefy · 2012-05-22 05:06:59

Do you know the Fundamental Theorem of Arithmetics? It can be used here.

careless25 · 2012-05-22 05:25:29

I just looked it up, I am not sure how to apply it though.
i am guessing we show, a,b,c have some prime factors since all of them have the same prime factor, the statement should be true.

EDIT:
This is what i have so far:

Let a = p1 * p2 where pN is an integer and a prime.
Let b = p3 * p4 " " " """
Let c = p5* p6 " " " " "

Now i am not sure how to show that a,b,c have the same unique prime factor.

Last edited by careless25 (2012-05-22 05:35:39)

anonimnystefy · 2012-05-22 05:40:02

No,Wait a sec,it isn't true for a=2,b=1024,c=4!!!

careless25 · 2012-05-22 05:46:10

Yes it does

GCD(8,1024) = 8
GCD(2,1024) = 2
GCd(4,1024) = 4

hence 8 = 4*2

anonimnystefy · 2012-05-22 05:54:58

No,you didn't substitute correctly.

GCD(1024,4)=4
GCD(512,4)=4
GCD(2,4)=2

2*4<>4

Sorry,I took b=512. You can see that we have a counterexample so the claim is false.

Last edited by anonimnystefy (2012-05-22 05:56:06)

careless25 · 2012-05-22 06:06:54

Wow that was that easy! thanks!

C25

anonimnystefy · 2012-05-22 06:10:17

Where did you get that question?

careless25 · 2012-05-22 06:25:51

It was a homework question on one of my assignments.

anonimnystefy · 2012-05-22 06:31:43

What was the wording of the question?

careless25 · 2012-05-22 07:25:01

it said for all a,b,c in intergers prove the following:

GCD(ab,c) = GCD(a,c) * GCD(b,c)

so a counterexample proves it false since it is for all a,b,c.

Math Is Fun Forum

#1 2012-05-21 14:19:33

Proof by induction?

#2 2012-05-21 16:55:57

Re: Proof by induction?

#3 2012-05-22 03:29:36

Re: Proof by induction?

#4 2012-05-22 04:09:42

Re: Proof by induction?

#5 2012-05-22 04:49:04

Re: Proof by induction?

#6 2012-05-22 05:06:59

Re: Proof by induction?

#7 2012-05-22 05:25:29

Re: Proof by induction?

#8 2012-05-22 05:40:02

Re: Proof by induction?

#9 2012-05-22 05:46:10

Re: Proof by induction?

#10 2012-05-22 05:54:58

Re: Proof by induction?

#11 2012-05-22 06:06:54

Re: Proof by induction?

#12 2012-05-22 06:10:17

Re: Proof by induction?

#13 2012-05-22 06:25:51

Re: Proof by induction?

#14 2012-05-22 06:31:43

Re: Proof by induction?

#15 2012-05-22 07:25:01

Re: Proof by induction?

Board footer