Welcome! Log In Create A New Profile

Advanced

Induction help please please

Posted by rezrovs 
Announcements Last Post
Announcement myUnisa availability 21 to 24 March 2019 03/17/2019 02:24PM
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Induction help please please
November 06, 2007 09:39AM
I'm working on some induction examples and I'm really hoping that someone can help me out with the examples that use inequalities.

For example, I'm looking at this example at the moment.

Formulate the induction principle for the set P of all positive numbers greater than or equal to 5. Then apply the induction principle to prove that 2n-3 <= 2^(n-2)

So I define a subset of P called A and I check that 5 is an element of A.

Then I go on to prove that k+1 is in A by assuming that k is in A. And it's here that I get unstuck.

The model answer is as follows

line 1) LHS = 2(k+1) - 3 = 2k + 2 - 3 = (2k-3) + 2
line 2) <= 2^(k-2) + 2 (from induction assumption)
line 3) <= 2.(2^(k-2)) (because the smallest value for 2^(k-2), k = 5 is 2^(5-2) = 8 and 2*8=16 > 10)

line 4) = 2^(1 + k - 2)
line 5) = 2^((k + 1) - 2)

Hence A = P and we conclude that 2n-3 <= 2^(n-2) for all n >= 5


Please could someone explain to me where the 2. comes from in line 3 and why the +2 goes away.

Many many many thanks,
Rachel
Re: Induction help please please
November 06, 2007 12:48PM
Hey there.

This is how I understand it.

If you put it in the form :
2^(k-2) + 2 <= 2.(2^(k-2))
The 2.(2^(k-2)) will always be bigger than 2^(k-2) + 2 if you substitute k with 5 or anything above it.

It is just easier to prove line 3 than it is line 2, and therefor they just substituted line 2 with something that will always be bigger than it!

Hope this makes some sense to you!

Good luck!!smile
Re: Induction help please please
November 06, 2007 12:58PM
Hi Zee01

So if I understand you, the 2. that I mentioned doesn't get derived from anything, it's just put in there to make the proof easier. And they used a 2 so that the next line would be 2^(1 + k - 2) and one can use that to get to line 5.

It also does make more sense seeing the lines side by side instead of underneath each other.

Thanks a bunch! smiling smiley
Rachel
Re: Induction help please please
November 06, 2007 01:03PM
Yip! Thats what I understand from it!

Multiplying something with 2 will always give a bigger answer that adding by 2?!

So it is not derived from the +2...

Its a pleasure!

Enjoy your day!

Zee
Re: Induction help please please
November 06, 2007 01:05PM
Thanks Zee. Good luck for the exam smiling smiley
Anonymous User
Re: Induction help please please
November 09, 2007 11:25AM
The way that I worked it out from the link I posted (and not from the irritatingly chatty study guide) is as follows:

hypothesis: 2n - 3 <= 2^(n - 2)
base case: check validity for n = 5
           2(5) - 3 <= 2^(5 - 2)
                  7 <= 8  
yay. base case checks out.
by induction, assume that the hypothesis for n - 1 is correct
then for n you have:

  2(n - 1) - 3 <= 2^(n - 1 - 2)   //hypothesis - 1
        2n - 5 <= 2^(n - 3)       //simplify
        2n - 3 <= 2^(n - 3) + 2   //add 2 to each side 
               <= 2^(n - 2)       //which was required to prove

So. ammirite?
Re: Induction help please please
November 09, 2007 11:31AM
I thought that for this example the induction principle would be

If A is a subset of P such that A contains 5 and such that A contains k+1 whenever it contains k, the A is in fact equal to P.

So then, Rick, why do you test for n-1? Is my induction principle wrong?
Anonymous User
Re: Induction help please please
November 09, 2007 11:44AM
#  Induction is the tool for proving an infinite set of related facts.

   1. Prove one fact (basis step).

   2. Show how the truth of the fact for any value of n immediately implies the truth of the fact for the value n + 1 (inductive step).

          * Break the inductive step into 3 carefully labeled sections.

               1. Inductive hypothesis: the fact for value n that you will assume to be true.

               2. Statement to be proven: the fact for value n+1 that you will prove to be true (very similar in form to the inductive hypothesis).

               3. Proof of inductive step: The proof that the inductive hypothesis implies the truth of the statement to be proven.

    * In this way, we can prove an infinite set of facts in a finite amount of time.

I think you are right Rachel, and I got my sets wrong. So the hypothesis will be true if we can squeeze it between a starting value (base case) and a value, hypthesis plus one. (Assuming a continuous function i suppose)
so let me correct my math:
  2(n + 1) - 3 <= 2^(n + 1 - 2)   //hypothesis + 1
        2n - 1 <= 2^(n - 1)       //simplify
        2n - 3 <= 2^(n - 1) - 2   //subtract 2 from each side 
               <= 2^(n - 2)       //which was required to prove
Re: Induction help please please
November 09, 2007 11:47AM
Whew, ok. I got nervous there!

And your example makes a lot more sense to me (with subtracting 2 from each side) than the tutorial letter on randomly multiplying one side by 2.

Thanks Rick smiling smiley
Anonymous User
Re: Induction help please please
November 09, 2007 11:47AM
rezrovs Wrote:
-------------------------------------------------------
> If A is a subset of P such that A contains 5 and
> such that A contains k+1 whenever it contains k,
> the A is in fact equal to P.

I don't understand this statement.
Anonymous User
Re: Induction help please please
November 09, 2007 12:01PM
Let S be a well-ordered set with the additional property that every element except for the smallest one has an immediate predecessor. Then: if Q is a property such that:

1. the smallest element of S has the property Q
2. if s element of S has property Q then the successor of s also has property Q

Then the property Q holds for every element in S
Re: Induction help please please
November 09, 2007 12:01PM
Is this only in the study guide?
Anonymous User
Re: Induction help please please
November 09, 2007 12:02PM
This stuff I'm getting from the internet. The study guide goes along one tangent only. I sometimes need the drier stuff to understand.
Re: Induction help please please
November 09, 2007 12:16PM
Its not covered in the textbook though, is it?
Anonymous User
Re: Induction help please please
November 09, 2007 12:18PM
Um, induction is definitely covered in the exam.
Re: Induction help please please
November 09, 2007 12:33PM
I understand its part of the syllabus but is it in the textbook and in the study guide or just in the study guide?
Anonymous User
Re: Induction help please please
November 09, 2007 12:37PM
Did you find it in the textbook?
Re: Induction help please please
November 09, 2007 12:37PM
I'm pretty sure it's only in the study guide and it's one of the first chapters.
Re: Induction help please please
November 09, 2007 01:06PM
thank Rexrovs - that's all I needed to know.

No Rick, I don't remember seeing it in the textbook but I wasn't sure if I had missed it or if it wasn't there to start with.
No need for a sarcastic reply.
avatar Re: Induction help please please
November 09, 2007 01:14PM
Tracey, I'll go and check, but last year, I didn't really work with the study guide and that example of the induction was in the textbook somewhere.
Re: Induction help please please
November 09, 2007 01:15PM
Sure thing. I was going to try find the guide online just to confirm, but myunisa looks down at the moment. But yip, pretty sure. I got through the textbook and was feeling all confident, and then i remembered that we got a study guide for this module. Doh!!
Anonymous User
Re: Induction help please please
November 09, 2007 01:26PM
The study guide covers recursion in considerably more detail than the textbook, you need to go through it.
Re: Induction help please please
November 09, 2007 01:38PM
Tracey Wrote:
-------------------------------------------------------
> No need for a sarcastic reply.

All good, I understand where you were coming from.
avatar Re: Induction help please please
November 10, 2007 08:39AM
Hi, I was thinking about the example on page 21 - 22. The induction method is not obviously used in that, so it seems the best examples is in the study guide. I remember that we did get a question on recursive definitions in last year's exam.
Sorry, only registered users may post in this forum.

Click here to login