Skip to content

It should be true for n=k+1 or why I.H. works

April 17, 2014

By I.H. we mean byInductiveLeaf induction hypothesis.

First year in maths students are baffled about mathematical induction(M.I.). It is counter intuitive and it is true, it is hard to wrap one’s head around this concept. So to prove some mathematical property holds we are given the following template:

  1. First show that the property P ( the property of being divisible, being prime or equal to a formula’s value, you name it etc.) is true for the base case. If the base case is c then we prove that the property is true for it. Thus we work on showing P(c) is true.
  2. Second, we assume it is true for k, that is P(k) is true – we take this as fact. This second step is called the induction hypothesis – I.H.
  3. Lastly, we prove that P(k+1) is true as well using I.H. Thus should we succeed in this final step, we have all the right to claim that we have proof that P is true for all n.

It is I.H. that is hard to take. Why is it that a.) we should assume it and b.) why is it that if step 3 succeeds provided we use the fact of step 2, we have the right to say – Q.E.D. or say “proven as required”! What right do we have in assuming I.H.

There are a few comments that we can make about this:

  • Firstly, M.I. is about the property of numbers (in general). Numbers obey this I. H. property. As a classic example consider a number x such that x > c, for some number like 8. So if we have x > 8, can we say that the next number after x will also be greater than 8? We can guess that this should be true. So let us prove it…Consider x > 8, let us add 1 to both sides still maintaining the inequality. x > 8 \Rightarrow x + 1 > 8 + 1 = 9 > 8 \therefore x + 1 > 8.
  • Secondly, we are allowed to assume I.H. for after all we can set our n = c, i.e., to our base case and check if the property P(c+1) holds — thus by the same token we are allowed to move from the truth of P(c) to the truth that P(c+1). So we can assume I.H. because of this “domino effect”. The crucial bit is to show now that due to our utilisation of I.H. for an arbitrary n = k, we get the truth of P(k+1).
  • Lastly and strongly, we can take M.I. to be an axiom! Meaning, a proposition which is self-evidently (if I can use that word) true! Indeed Wikipaedia has it like this – \forall P[P(0) \wedge \forall k \in \mathbb{N}[P(k) \Rightarrow P(k+1)]] \bold{\Rightarrow} \forall n \in \mathbb{N}[P(n)].
  • Take a good look at this and consider the statement before the last \Rightarrow. If you look we have this form A \Rightarrow B. Remember modus ponens? It says if we have A \Rightarrow B and we have A, deduce B.

Well when we are doing M.I. what we are actually doing is that we are establishing the truth of A and when we succeed – voila, use this with the axiom and so conclude the property P holds for all n.

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: