How Is the Inductive Hypothesis Used in Proof Writing?

[TrevE]

I'm practicing induction and proof-writing, and I have a small query. How do we use the inductive hypothesis in our closing argument? Can we equate it to a statement proved by a lemma? For instance, do we assume that the inductive hypothesis is true in the (n+1) case all the time?

Also, can we assume that b+c = a, when a = b+c?

 

[matt grime]

Unless you are doing something very strange with the equals sign, then it is symmetric like that.

I don't really understand the first query. Try writing out an example of how you would write a proof (by induction).

 

[Office_Shredder]

Inductive proof:

First, show that your statement is true for n=1 (or 2 or 3, depending on what you're proving, but generally a really small number. 1 should work).

Then, assume it's true for n=k. Check if your statement is true for k+1 by plugging it into your statement, then performing (usually) basic algebraic manipulations to get your equation into something that looks like you plugged in n=k, and added or multiplied a trivially true statement

 

[matt grime]

Modulo the fact that most statements proved using induction have nothing to do with adding or multiplying by other statements since they are generically going to be questions like that, and it makes no sense to talk of adding or multiplying logical statements.

They key is to relate statement P(k+1) to P(k), and show that the either P(k) implies P(k+1), or that the negation of P(k+1) implies the negation of P(k) using what ever makes sense (which will not generically be by adding things together). A very common technique is to assume that there is a minimal counter example (minimal for k) and then show that this implies the existence of a smaller one.

 

[HallsofIvy]

I'm practicing induction and proof-writing, and I have a small query. How do we use the inductive hypothesis in our closing argument? Can we equate it to a statement proved by a lemma? For instance, do we assume that the inductive hypothesis is true in the (n+1) case all the time?

I'm not at all clear what you mean by "assume the inductive hypothesis is true in the (n+1) case". The second step in proof by induction (the first is showing the statement is true for n= 1) is to prove that "If the statement is true for some n (that's the "inductive hypothesis) then the statement is true for n+1". We don't "assume that the inductive hypothesis is true in the (n+1) case"- the inductive hypothesis is that the statement to be proved is true for some n. We then have to prove that, with that hypothesis, the statement is also true for n+1.

Also, can we assume that b+c = a, when a = b+c?

Well, yes, that is a basic property of "= ". If fact, it is one of the requirements (symmetry) for any equivalence relation, of which "=" is the "prototype".

 

[TrevE]

Thanks for the clarification everyone! For what's it worth, the [very simple] problem was:

Prove that for any natural number n, n++ = n+1.

Here's what I came up with after reading your replies:

We use induction. We first consider the base case n=0, for which we have to prove that 0++ = 0+1. We first observe that 0++ = 1 by definition [1], and 0+1 = (0+0)++ = 0++ = 1 by Lemma 2 [2]. Thus the base case is done. Now suppose inductively that n++ = n+1; we now have to prove that (n++)++ = (n++) + 1. The right-hand side is (n+1)++ by definition of addition [3], but by the inductive hypothesis, (n+1)++ = (n++)++, and we have closed the induction.

[1] We define: 1 := 0++, 2 := 1++, 3 := 2++, and so on.
[2] For any natural number n and m, n+(m++) = (n+m)++.
[3] Let m be a natural number. To add 0 to m, we define 0+m := m. Now suppose inductively that we have defined how to add n to m. Then we can add n++ to m by defining (n++) + m := (n+m)++.

I'm not very sure I did things right since I'm very new at this. Also, I wasn't totally sure that the equality is symmetrical at all times, but obviously it is.

 

[matt grime]

What on Earth is n++? That thing in smaller text?Since the definition of your operation appears to be that n+1 = n++ there is nothing to prove at all.

If however we change [1] so it only defines 0++ as 1, and use the other rules then,

(n+1)++ = (n++)+1 by rule 2, which is n+1+1 using the inductive hypothesis (that n++=n+1) which is n+2 and we are done.

 

[TrevE]

The smaller text is from my lecture notes--my professor defines incrementation as n++, but at that point, we didn't introduce addition so we didn't equate it to n+1. Then we defined addition as recursive incrementation, and we proved a few propositions and lemmas. At that point we were asked to prove the above simple result. Sorry for not clarifying this earlier.

 

[matt grime]

But part [1] clearly states that the symbol n++ is the same as n+1, unless there is some odd interpretation of what 'and so on' should mean, and there is nothing to prove whatsoever. This has nothing to do 'operations' such as addition. I suspect that it is one of those things you do when writing lecture notes of making up some 'bad' questions in an attempt to make it simple and understandable. Of course, he could just be trying to get you to rigorously demonstrate what the 'and so on' is hiding.