1

What are different ways in which I can use a two dimensional mathematical induction? I will also appreciate any examples of its use.

By this I mean the principle that will be used when I have to prove a theorem for all $(x,y)$ by showing that it is true for $(0,0)$ and also if (assumption) it's true for $(x,y)$ implies it is true for $(x+1,y)$ and also $(x,y+1)$.

Shubham Ugare
  • 703

1 Answers1

5

Hope I understand your question correctly. You have to prove some statement S(n,m) for every n and every m, where n and m are positive integers. I usually do it like this:

1) I prove it's true for n=1 and every m.
2) I assume it's true for n=1,2,...,k (or for n=k only), and for every m.
3) I prove it's true for n=k+1 and for every m.

From this I conclude that it's true for every n and every m.

As in 1), 2), 3) I always do "every m", I would not call this two-dimensional though. Of course while proving 1) and 3), you're free to do another/nested induction on m. It could be that's what you meant in your question. Just make sure you don't use something which you haven't proved yet (it's easy to get confused and mess up by providing a flawed proof).

peter.petrov
  • 12,568
  • why would you not call it two dimensional? – Shubham Ugare May 15 '15 at 21:45
  • If I do another/nested induction (on m) while proving 1) or 3) - yes, I would call it. But if I just prove 1) and 3) directly (for every m, without another induction on m), then m does not really play in the game. It's like you're proving a statement T(n), where m doesn't play, by a normal induction. – peter.petrov May 15 '15 at 21:47
  • okay.I get it.what you mean to say but step 1) that you are doing may not always work directly. – Shubham Ugare May 15 '15 at 21:52
  • Can you rephrase your question? I don't get it. – peter.petrov May 15 '15 at 21:54
  • step 1) in the process that you used may not be possible always and it may require induction . I would call that double induction. Right? – Shubham Ugare May 15 '15 at 21:56
  • In that sense, yes, that's right, then I would call it double induction (not sure of the original English term). The same goes for step 3. – peter.petrov May 15 '15 at 21:59
  • thanks. your method helped me .I can't vote though as I have just started using stack exchange and it doesnt allow voting. – Shubham Ugare May 15 '15 at 22:01
  • @ShubhamUgare No worries :) I am here for fun mostly, not for the rating. – peter.petrov May 15 '15 at 22:05