Math Is Fun Forum

Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫  π  -¹ ² ³ °

You are not logged in.

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Proof by induction?

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)

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,048

Re: Proof by induction?

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)

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Proof by induction?

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)

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,048

Re: Proof by induction?

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

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Proof by induction?

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)

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,048

Re: Proof by induction?

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

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Proof by induction?

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)

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,048

Re: Proof by induction?

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

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Yes it does

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

hence 8 = 4*2

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,048

Re: Proof by induction?

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)

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Proof by induction?

Wow that was that easy! thanks!

C25

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,048

Re: Proof by induction?

Where did you get that question?

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Proof by induction?

It was a homework question on one of my assignments.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,048

Re: Proof by induction?

What was the wording of the question?

Here lies the reader who will never open this book. He is forever dead.
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Proof by induction?

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.

Offline