Inducción sobre dos variables enteras

Question

Suponga que quiere probar una identidad como

$$ \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.$$

Añadido : Apliqué la inducción matemática en $m,n$ para probarlo. No estoy seguro porque hasta ahora lo he visto aplicado a propiedades que dependen de una sola variable.

Pregunta: ¿la aplicación de dos argumentos inductivos, uno sobre $m$ y el otro en $n$ garantizar la validez de tal prueba?

Answer 1

He aquí algunos principios de inducción para dos 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)$

y

• $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)$

Answer 2

Supongamos que se trata de demostrar una familia de afirmaciones $P(x, y)$ . Esto es lo mismo que demostrar la familia de afirmaciones $F(x)$ , donde $F(x) = \forall y : P(x, y)$ . Cada declaración $F(x)$ se puede demostrar por inducción en $y$ (para los fijos $x$ ), y entonces puedes probar $P(x, y)$ por inducción en $x$ . Tal vez quieras probar

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

de esta manera.

Pero en realidad puede ser mucho más complicado que esto. A veces basta con inducir en $x + y$ por ejemplo.