Suppose I want to prove $p(m,n)=1/2$ for all $m\ge1,n\ge1$, and I know the base case $p(1,1)=1/2$ holds.

Here is my induction proof:

  1. assume $p(m-1,n),p(m,n-1),p(m-1,n-1),p(m-2,n-1)\cdots$ all equals to $1/2$.
  2. with above assumption, show that $p(m,n)=1/2$.

Is above induction logically rigorous? why and why not?


This question is my analogy to a single variable problem, which is like this:

Suppose we want to prove $p(n)=1/2$ holds for any positive integer $n$, it is easy to show that $p(1)=1/2$. Assuming $p(k)=1/2$ holds for all $k<n$, using this, prove $p(n)=1/2$.

This is the standard way to make an induction proof.

  • $\begingroup$ For $m$ you can keep $n$ constant and prove for $m+1$ for example, assume $p(m,n_0)=1/2$ and prove for $p(m+1,n_0)$. And use the same idea for prove in $n$. $\endgroup$ – Arnaldo Dec 9 '16 at 13:27
  • $\begingroup$ @ArnaldoNascimento Are you saying that my proof is not rigorous? Can you show why? $\endgroup$ – fizis Dec 9 '16 at 13:29
  • $\begingroup$ You don't need all of them, in general. Just $p(m-1,n)$ when you are try to prove for $m$. But maybe you need both depending what information you have. If you put all information for the problem one can help you better. $\endgroup$ – Arnaldo Dec 9 '16 at 13:32
  • $\begingroup$ @ArnaldoNascimento I am raising a general question... $\endgroup$ – fizis Dec 9 '16 at 13:34
  • $\begingroup$ Are you asking about induction on $\mathbb{N}\times \mathbb{N}$? $\endgroup$ – user 170039 Dec 9 '16 at 13:55

Really it depends on what is happening along the edges (when $m$ or $n$ is $1$). If your induction argument requires for instance that $p(2,0)$ be equal to $\frac12$ in order for $p(2,1)$ to be equal to $\frac12$, then your argument is not valid.

For instance $p(1,1) = \frac12$ and $p(m,n) = 5$ for all $(m,n)\ne (1,1)$ would be a counterexample.

  • $\begingroup$ there is no case of $p(2,0)$ and such, and the edges is included in the assumption I think. $\endgroup$ – fizis Dec 9 '16 at 14:34
  • $\begingroup$ You seem to say if we add the information that $p(1,n)=1/2, p(m,1)=1/2$ for all $m$ and $n$, then my induction is correct. Do I understand correctly? $\endgroup$ – fizis Dec 10 '16 at 16:52
  • $\begingroup$ Albeit you didn't reply to my concerns, I think your answer might be right. so I accept it. $\endgroup$ – fizis Dec 11 '16 at 15:40

The following induction principle is sound:

Suppose that $p(1,1)$ holds, and, for all $u,v \in \mathbb{N}$, if $p(u,v)$ holds then $p(u+1,v)$ and $p(u,v+1)$ hold. Then $p(n,m)$ holds for all $n,m \in \mathbb{N}$.

To see that the principle is sound, notice that for any $n,m \in \mathbb{N}$ we have a chain $$ p(1,1), p(2,1), \ldots, p(m,1), p(m,2), \ldots, p(m,n).$$ By assumption, the first formula in the chain is true, and each formula implies the next, so the last one is true.

It is possible to convert the rule into one analogous to "strong induction", which is more cumbersome to state. It weakens the inductive assumption to say that $p(u+1, v)$ and $p(u,v+1)$ must hold if $p(x,y)$ holds for all $x \leq u$ and $y \leq v$.

  • $\begingroup$ Your induction procedure is alright, and your weaker assumption is also true with the same chain you present. What about mine induction? right or wrong? @N.S says it is right, you seems avoided... $\endgroup$ – fizis Dec 10 '16 at 16:34
  • $\begingroup$ I have a hard time understanding the exact principle you were proposing, so I wrote something that I think gets at what you wanted, but which I could understand more clearly. I think that the second principle I mentioned (the "strong" version) should be the same as what you suggested. $\endgroup$ – Carl Mummert Dec 10 '16 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.