Posted by rezrovs
Announcements Last Post
myUnisa availability 21 to 24 March 2019 03/17/2019 02:24PM
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Induction help please please November 06, 2007 09:39AM Registered: 12 years ago Posts: 308 Rating: 0
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 Registered: 11 years ago Posts: 38 Rating: 0
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!!
 Re: Induction help please please November 06, 2007 12:58PM Registered: 12 years ago Posts: 308 Rating: 0
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!
Rachel
 Re: Induction help please please November 06, 2007 01:03PM Registered: 11 years ago Posts: 38 Rating: 0
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!

Zee
 Re: Induction help please please November 06, 2007 01:05PM Registered: 12 years ago Posts: 308 Rating: 0
Thanks Zee. Good luck for the exam
 Anonymous User Re: Induction help please please November 09, 2007 11:25AM Rating: 0
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 Registered: 12 years ago Posts: 308 Rating: 0
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 Rating: 0
```#  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 Registered: 12 years ago Posts: 308 Rating: 0
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
 Anonymous User Re: Induction help please please November 09, 2007 11:47AM Rating: 0
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 Rating: 0
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 Registered: 13 years ago Posts: 3,249 Rating: 0
Is this only in the study guide?
 Anonymous User Re: Induction help please please November 09, 2007 12:02PM Rating: 0
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 Registered: 13 years ago Posts: 3,249 Rating: 0
Its not covered in the textbook though, is it?
 Anonymous User Re: Induction help please please November 09, 2007 12:18PM Rating: 0
Um, induction is definitely covered in the exam.
 Re: Induction help please please November 09, 2007 12:33PM Registered: 13 years ago Posts: 3,249 Rating: 0
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 Rating: 0
Did you find it in the textbook?
 Re: Induction help please please November 09, 2007 12:37PM Registered: 12 years ago Posts: 308 Rating: 0
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 Registered: 13 years ago Posts: 3,249 Rating: 0
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.
 Re: Induction help please please November 09, 2007 01:14PM Registered: 13 years ago Posts: 3,015 Rating: 5
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 Registered: 12 years ago Posts: 308 Rating: 0
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 Rating: 0
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 Registered: 13 years ago Posts: 3,249 Rating: 0
Tracey Wrote:
-------------------------------------------------------
> No need for a sarcastic reply.

All good, I understand where you were coming from.
 Re: Induction help please please November 10, 2007 08:39AM Registered: 13 years ago Posts: 3,015 Rating: 5
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.