Posted by rezrovs

Announcements | Last Post | |
---|---|---|

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

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!!

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

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 |

Re: Induction help please please November 06, 2007 01:05PM |
Registered: 12 years ago Posts: 308 Rating: 0 |

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:

So. ammirite?

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 |

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 |

Anonymous User
Re: Induction help please please November 09, 2007 11:47AM |
Rating: 0 |

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

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 |

Anonymous User
Re: Induction help please please November 09, 2007 12:02PM |
Rating: 0 |

Re: Induction help please please November 09, 2007 12:16PM |
Registered: 13 years ago Posts: 3,249 Rating: 0 |

Anonymous User
Re: Induction help please please November 09, 2007 12:18PM |
Rating: 0 |

Re: Induction help please please November 09, 2007 12:33PM |
Registered: 13 years ago Posts: 3,249 Rating: 0 |

Anonymous User
Re: Induction help please please November 09, 2007 12:37PM |
Rating: 0 |

Re: Induction help please please November 09, 2007 12:37PM |
Registered: 12 years ago Posts: 308 Rating: 0 |

Re: Induction help please please November 09, 2007 01:06PM |
Registered: 13 years ago Posts: 3,249 Rating: 0 |

Re: Induction help please please November 09, 2007 01:14PM |
Registered: 13 years ago Posts: 3,015 Rating: 5 |

Re: Induction help please please November 09, 2007 01:15PM |
Registered: 12 years ago Posts: 308 Rating: 0 |

Anonymous User
Re: Induction help please please November 09, 2007 01:26PM |
Rating: 0 |

Re: Induction help please please November 09, 2007 01:38PM |
Registered: 13 years ago Posts: 3,249 Rating: 0 |

Re: Induction help please please November 10, 2007 08:39AM |
Registered: 13 years ago Posts: 3,015 Rating: 5 |

Sorry, only registered users may post in this forum.