Proof by mathematical induction

Proof method: Multidimensional induction

For the last couple of posts we have been dealing with mathematical induction. This post shall be no different. However, until now we have been limited to one variable, so this post will deal with induction on multiple variables – or in other words multidimensional induction as the headline suggests. 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.

If we have the statement P(m,n) then we need to prove three things:

  1. Basecase: We need to prove a base case P(a,b) where a is the smallest value for which m is valid and b is the smallest value where n is valid.
  2. Induction over m: We assume that P(k,b) is valid for some positive integer k. Then we need to prove that P(k+1,b) is valid.
  3. Induction over n: We assume that P(h,k) is valid for some positive integers h,k. Then we need to prove that P(h,k+1) is valid.

If we can prove these three things then we have proved that P(m,n) is true for all and . point 1 and 2 ensures that the statement is true for all P(m,a) just as in the in the single variable case. Once we have proven that then adding 3 ensures that it holds for all n as well. But let us take an example.

Example

Proposition: Let f(m,n) be a function with f(1,1) = 2 and

f(m+1,n) = f(m,n) +2(m+n)

f(m,n+1) = f(m,n) +2(m+n-1)

For all prove that f(m,n) = (m+n)2 – (m+n) – 2n +2

Proof:

Basecase: We need to check that (m+n)2 – (m+n) – 2n +2 = 2 for m,n = 1. So let us plug it into the formula. f(1,1) = (1+1)2 – (1+1) – 2 +2 = 4 – 2 – 2 + 2 = 2. So the base case  holds.

Induction on m: Assuming that the statement f(k,1) is true we need to prove that f(k+1,1) is true as well. For this we will use a direct proof.

f(k+1,1) = f(k,1) + 2(k+1)

The first part is f(k,1) = (k+1)2 – (k+1) – 2 + 2  = k2 +2k +1 – k – 1 = k2 + k by assumption which gives us

f(k+1,1) = (k2 + k) + 2(k+1) =

k2 + 3k + 2 =

k2 + 3k + 2  + k – j +2 -2 =

(k2 + 4k + 4) – (k + 2)

So far I rearranged the formula a bit and added k-k and 2-2 which I am allowed to, since you can always add 0. The first parantheses can be rewritten as a quadratic term since (k + 2)2 = (k2 + 4k + 4).

(k + 2)2 – (k + 2) =

((k + 1) + 1)2 – ((k+1) + 1)   + 2(1) – 2

Which proves that it holds for f(k+1,1).

Induction on n: Now we assume that the proposition holds for f(h,k) and we need to prove that it holds for f(h,k+1) as well. Once again we will use a direct proof to show this

f(h,k+1) = f(h,k) + 2(h+k – 1) =

(h+k)2 – (h+k) – 2k +2 + 2(h + k – 1) =

(h+k)2 – (h+k) – 2k +2 + 2(h + k) – 2

Since = (h+k)2 + 2(h+k) + 1 = (h+k+1)2 we can rewrite the equation to

(h+(k +1))2 – (h+k) – 2k – 1 =

(h+(k +1))2 – (h+k+1) – 2(k+1) + 2

which is equal to the proposition that f(h,k+1) = (h+(k +1))2 – (h+k+1) – 2(k+1) + 2.

From these three cases it follows that f(m,n) = (m+n)2 – (m+n) – 2n +2 for all all natural number m,n.

Wrapping up

There is another method for conducting inductive proofs  in the multidimensional case, it is covered nicely in this note. It builds on assuming that for any m+n = k the proposition holds and we then need to show that it holds for m+n = k+1.

The metaphor of dominoes also gave rise to the chosen post photo, which was kindly shared under the creative common license by Malkav. My crop of the photo is of course shared under the same conditions.

Posted by Kristian

4 comments

[…] found this linked in a similar question: http://www.mathblog.dk/proof-method-multidimensional-induction/ where it says it’s necessary to do induction on each variable. Is this tacitly omitted in […]

[…] found some help regarding multidimensional induction in a blogpost, but I don’t know how to approach the […]

[…] found this blog post with a good example of 2D induction. It seems in this example, 2D induction is needed […]

i liked this blog an i need help as I want to prove that sum of n sqauare numbers is not equal sum of other n square numbers I have no idea how to do it .i will be very glad if you help me.

Leave a Reply