Math Is Fun Forum

user1

Member

Registered: 2009-11-17

Posts: 2

proof help!

Hi

This are two questions that have given me a big trouble for sometime. I would be apperciate any help in solving this two questions.

Question1:

Let

be a subset of the natural numbers which has the following porperty :

Prove by contradiction that

in fact consists of all the natural numbers, i.e. prove that

Question2:

Prove by induction that:

Where

are Fibonacci sequence.

Last edited by user1 (2009-11-18 00:12:57)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: proof help!

For the first one, I assume you're also told that 1 is in S?  If there are natural numbers not in S, remember you can always find the smallest one not in S.

For the 2nd one, start writing up the induction here and stop whenever you don't see what to do.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

user1

Member

Registered: 2009-11-17

Posts: 2

Re: proof help!

Yes, 1 is in S. For the second question, I know as far as inductive step:- k+1.  After that I don't know how to make the L.H.S equal to R.H.S.