# Basic proof writing and induction

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:

matt grime
Homework Helper
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
Staff Emeritus
Gold Member
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
Homework Helper
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:
HallsofIvy
Homework Helper
TrevE said:
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.

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.

Last edited by a moderator:
matt grime
Homework Helper
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:
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