Posts Tagged with "Induction"

Proof by mathematical induction

Proof method: Multidimensional induction

Wednesday, August 24, 2011

0 Comments

For the last couple of posts we have been dealing with mathematical induction, I will pick up where we left and continue on this topic one more time. Many introductions to proof by induction covers only the one dimensional case, here is an introduction to multidimensional induction. I will treat the two dimensional case in this post, but the expansion to n dimensions should be relatively easy. So for now we will assume that we have a statement P(m,n) which we need to prove.

Continue reading...
Proof by mathematical induction

Proof method: Strong Induction

Wednesday, August 10, 2011

10 Comments

As I promised in the Proof by induction post, I would follow up to elaborate on the proof by induction topic. Here is part of the follow up, known as the proof by strong induction. What I covered last time, is sometimes also known as weak induction.In weak induction the induction step goes: Induction step: If P(k) is true then P(k+1) is true as well.Strong induction expands that to: Induction step: If P(b), P(b+1), P(b+2)... P(k) is true then P(k+1) is true as well for some k > b.

Continue reading...
Proof by mathematical induction

Proof methods: Proof by mathematical induction

Wednesday, August 3, 2011

4 Comments

It has been a while since I last posted something about proof methods, but lets dig that up again and take a look at a fourth method. The first three were direct proof, proof by contradiction and contrapositive proofs. Proof by induction is a somewhat different nature.Induction usually has it's force on statements of the type "For all integers k greater than b, P(k) is true". For some statements we could prove it with some of the already covered methods, but for others it would mean that we had to prove an infinity of cases.The analogy I see everywhere and which I find quite fitting is to compare induction to dominoes (and I don't mean the pizza thing) which are lined up. As soon as you knock the first one over it knocks all the remaining once over one by one. Induction works in much the same way.

Continue reading...