Induction help please please

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

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

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

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

Thanks Zee. Good luck for the exam

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?

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?

#  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

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

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.

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

Is this only in the study guide?

This stuff I'm getting from the internet. The study guide goes along one tangent only. I sometimes need the drier stuff to understand.

Its not covered in the textbook though, is it?

Um, induction is definitely covered in the exam.

I understand its part of the syllabus but is it in the textbook and in the study guide or just in the study guide?

Did you find it in the textbook?

I'm pretty sure it's only in the study guide and it's one of the first chapters.

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.

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.

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

The study guide covers recursion in considerably more detail than the textbook, you need to go through it.

Tracey Wrote:
-------------------------------------------------------
> No need for a sarcastic reply.

All good, I understand where you were coming from.

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.