Basic proof writing and induction

1. Sep 15, 2006

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?

Last edited by a moderator: Sep 16, 2006
2. Sep 16, 2006

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).

3. Sep 16, 2006

Office_Shredder

Staff Emeritus
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

4. Sep 16, 2006

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.

Last edited: Sep 16, 2006
5. Sep 16, 2006

HallsofIvy

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.

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".

6. Sep 16, 2006

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.

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.

Last edited by a moderator: Sep 16, 2006
7. Sep 16, 2006

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.

Last edited: Sep 16, 2006
8. Sep 16, 2006

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.

9. Sep 16, 2006

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.

Last edited: Sep 16, 2006