Demuestre formalmente por inducción que $f^k(m, n) = (m − kn, n)$ para todos $k\in\Bbb Z^+$ .

Question

Entiendo en general cómo funciona una prueba de inducción, sin embargo estoy teniendo dificultades con la siguiente pregunta:

Sea $f :\Bbb Z^2 \to\Bbb Z^2$ viene dada por $f(m, n) = (m n, n)$ . Las funciones compuestas $f^k$ para $k\in\Bbb Z^+$ se definen como $f^1(m, n) = f(m, n)$ y $f^{k+1}(m, n) = f(f^k(m, n))$ para $k\in\Bbb Z^+$ . Demuestre formalmente por inducción que $f^k(m, n) = (m kn, n)$ para todos $k\in\Bbb Z^+$ .

Ni siquiera estoy seguro de cual sería el paso base ya que es una función compuesta... una explicación de los pasos para resolverlo sería de gran ayuda Gracias por su ayuda

Answer 1

SUGERENCIA: El paso básico es demostrar que la afirmación es cierta para $k=1$ es decir, que

$$f^1(m,n)=(m-1\cdot n,n)$$

para todos $m,n\in\Bbb Z$ . Se trata simplemente de comprobar la definición de $f^1$ .

Para el paso de inducción tomarás como hipótesis de inducción que $f^k(m,n)=(m-kn,n)$ para todos $m,n\in\Bbb Z$ y tratar de demostrar a partir de esto que

$$f^{k+1}(m,n)=\big(m-(k+1)n,n\big)\tag{1}$$

para todos $m,n\in\Bbb Z$ . Se trata de una aplicación directa del paso recursivo en la definición de las funciones $f^\ell$ : utilícelo para expresar $f^{k+1}(m,n)$ en términos de $f^k(m,n)$ y luego utilizar la hipótesis de inducción para simplificar eso, y usted tendrá sólo un poco de álgebra que hacer con el fin de obtener $(1)$ .

Answer 2

Para $k=1$ el argumento es fácil. Supongamos que la igualdad se cumple para $k$ aplique ahora la fórmula para $k+1$ implica que: $$f^{k+1}=f(f^k(m,n))=f(m-kn,n)=(m-kn-n,n)=(m-(k+1)n,n).$$