Give a formal proof by induction that $f^k(m, n) = (m − kn, n)$ for all $k\in\Bbb Z^+$.

Question

i understand in general how an induction proof works, however I'm having difficulties with the following question:

Let $f :\Bbb Z^2 \to\Bbb Z^2$ be given by $f(m, n) = (m − n, n)$. The composite functions $f^k$, for $k\in\Bbb Z^+$, are defined as $f^1(m, n) = f(m, n)$, and $f^{k+1}(m, n) = f(f^k(m, n))$ for $k\in\Bbb Z^+$. Give a formal proof by induction that $f^k(m, n) = (m − kn, n)$, for all $k\in\Bbb Z^+$.

I'm not even sure what the base step would be since it is a composite function... an exaplanation of the steps to solve it would be very helpful Thank you for your help

Answer 1

HINT: The base step is to show that the statement is true for $k=1$, i.e., that

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

for all $m,n\in\Bbb Z$. This is just a matter of checking the definition of $f^1$.

For the induction step you’ll take as your induction hypothesis that $f^k(m,n)=(m-kn,n)$ for all $m,n\in\Bbb Z$ and try to prove from this that

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

for all $m,n\in\Bbb Z$. This is a straightforward application of the recursive step in the definition of the functions $f^\ell$: use that to express $f^{k+1}(m,n)$ in terms of $f^k(m,n)$ and then use the induction hypothesis to simplify that, and you’ll have just a little algebra left to do in order to get $(1)$.

Answer 2

For $k=1$, the argument is easy. Suppose that the equality holds for $k$, now apply the formula for $k+1$ imlies that: $$f^{k+1}=f(f^k(m,n))=f(m-kn,n)=(m-kn-n,n)=(m-(k+1)n,n).$$