Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assume you want to prove an identity such as

$$\sum_{k=m+1}^{n}A(k,m)-B(k,m)=S(m)+T(n,m)\qquad\text{for } n,m\in \mathbb{Z},n,m\geq 0.$$

Added: I applied mathematical induction on $m,n$ to prove it. I am unsure because up to now I have seen it applied to properties depending on a single variable only.

Question: does application of two inductive arguments, one on $m$ and the other on $n$, guarantee the validity of such a proof?

share|improve this question
2  
Sure. Why wouldn't it? –  Qiaochu Yuan Oct 24 '10 at 9:29
    
@Qiaochu Yuan: Thanks! I asked it because I actually have not seen yet any proof of a two indices identity by this method. –  Américo Tavares Oct 24 '10 at 9:59
add comment

2 Answers 2

up vote 9 down vote accepted

Here are some induction principles for two variables:

  • $P(0,0)$
  • $\forall x,y. P(x,y) \Rightarrow P(x+1,y)$
  • $\forall x,y. P(x,y) \Rightarrow P(x,y+1)$


  • $\forall x,y. P(x,y)$

and

  • $P(0,0)$
  • $\forall x,y. P(x,0) \Rightarrow P(x+1,0)$
  • $\forall x,y. P(x+1,y) \Rightarrow P(x,y+1)$


  • $\forall x,y. P(x,y)$

share|improve this answer
    
@muad: in the 2nd example is it $\forall x,y. P(x+1,y) \Rightarrow P(x,y+1)$ or $\forall x,y. P(x,y) \Rightarrow P(x,y+1)$? –  Américo Tavares Oct 24 '10 at 11:04
    
@Américo Tavares, the second one is covering the x-axis and shifting diagonally back to cover everything above it. So it is $\forall x,y. P(x+1,y) \Rightarrow P(x,y+1)$. –  anon Oct 24 '10 at 11:11
    
@muad: I see now, thanks! –  Américo Tavares Oct 24 '10 at 11:22
    
+1 for the examples –  Américo Tavares Oct 24 '10 at 15:20
add comment

Suppose you are trying to prove a family of statements $P(x, y)$. This is the same as proving the family of statements $F(x)$, where $F(x) = \forall y : P(x, y)$. Each statement $F(x)$ can be proven by induction on $y$ (for fixed $x$), and then you can prove $P(x, y)$ by induction on $x$. You might want to try proving

$${n+1 \choose k+1} = {n \choose k+1} + {n \choose k}$$

this way.

But actually you can be much trickier than this. Sometimes it suffices to induct on $x + y$, for example.

share|improve this answer
    
+1 for the "logic" explanation and for the trick. –  Américo Tavares Oct 24 '10 at 15:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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