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

Re: Proof by induction?

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

Board footer

Powered by FluxBB