I'm working on the following exercise:
If $f_n : \mathbb{N} \to \mathbb{N}$ is a function we take $f^k(x)$ to denote the $k$-fold iteration $f(f(\ldots f(x)))$ of $f$ applied to $x$. In the special case $k = 0$, we take $f^0(x)$ to denote $x$.
Now define the sequence of functions $f_n : \mathbb{N} \to \mathbb{N}$, for $n \in \mathbb{N}$ as follows:
$f_0(0) = 1$;
$f_0(1) = 2$;
$f_0(x) = x + 2$ for $x > 1$;
$f_{n+1}(x) = f^k(x)$
Give an inductive proof that, for all $n$, $f_n$ is increasing: $x < y \implies f_n(x) < f_n(y)$.
What I've done:
I've done the base case:
I need to prove that $f_0(x) < f_0(y)$. If $x = 0$, $y = 1$ then $f_0(x) = 1$ and $f_0(y) = 2$, so $f_0(x) < f_0(y)$ so base case is OK.
But I don't really know what I need to do for the inductive step. I know I have to prove that $f_{n+1}(x) < f_{n+1}(y)$ but I'm not sure how to do that. Any steps/hints in the right direction would be very appreciated. Thanks!