How to prove that this function over nonnegative integers is monotonic? I am solving a functional equation:
$f:\mathbb N_0\rightarrow \mathbb N_0$,
$f(m^2+n^2)=f(m)^2+f(n)^2, \forall m,n \in \mathbb N_0$ and
$f(1)>0$
I've proved that $f(2^n)=2^n, \forall n \in \mathbb N_0$ and I've found  that $f(0)=0,f(1)=1,f(2)=2$. If I prove that the function is monotonic then I can prove that it is strictly increasing. So I can prove that the function is the identity map. Because then we would get
$$f(2^n)=2^n<f(2^n+1)<f(2^n+2)<\dots<f(2^{n+1})=2^{n+1}.$$
Since there are $2^n-1$ integers between $2^n$ and $2^{n+1}$, combining this with the above inequality gives $f(m)=m$ for all m such that $2^n \leq m< 2^{n+1}$.
 A: From $f(0^2+0^2)=f(0)^2+f(0)^2$, we have
$$ f(0)=0.$$
Then from $f(1^2+0^2)=f(1)^2+f(0)^2$ and $f(1)>0$, we have
$$ f(1)=1.$$
Let $$ S=\{\,n\in\Bbb N_0\mid f(n)=n\,\}.$$
As just seen, $\{0,1\}\subset S$. Also, if two of $n,m,n^2+m^2$ are $\in S$, then so is the third. In particular,
$$\tag1m\in S\iff m^2\in S. $$
Additionally, we extract
$$\tag2 m\in S\iff 2m^2\in S$$
from the functional equation.
From $(1)$ and $(2)$,
$$\tag3m\in S\iff 2m\in S. $$
Induction on $(3)$ gives us that $2^n\in S$ for all $n$, as you already know.
Just to get a feeling, here are proofs for a few more concrete values:
From $1,2\in S$, $5=1^2+2^2\in S$, then also $10=2\cdot 5\in S$, and from $1,10\in S$ also $3=\sqrt{10-1^2}\in S$.
From $5\in S$, we have $50=2\cdot 5^2\in S$, then with $1\in S$ also $7=\sqrt{50-1^2}\in S$. With $3=3^2\in S$, we have already found $\{0,\ldots,10\}\subset S$ and more. But note that we had to go up and down in many cases (e.g., $5\to 50\to 7$).
Induction:
Let $n\in\Bbb N_0$ and assume $k\in S$ for all $k<n$.
By the above, we may assume $n>10$. But if we wish to ignore our concrete computations for special cases, we can also work with the weaker $n>1$.
If $n$ is even, we use $(3)$ to see that $n\in S$ and are done.
So assume $n=2m+1$ is odd. Note that $m\ge 1$.
If we find $r,s,t$ with $n^2+r^2=s^2+t^2$ and $r,s,t<n$, we can conclude $n\in S$. So we rearrange as
$$(n+t)(n-t)=n^2-t^2=s^2-r^2=(s+r)(s-r).$$
Write $n=2m+1$. Then if we let $t=n-2$, the expression becomes
$$(n+t)(n-t)=(2n-2)(2)=(2m)(4) $$
hence with $s=\frac{2m+4}2=m+2$ and $r=\frac{2m-4}2=m-2$, we have $n^2+t^2=r^2+s^2$, as desired.
Note that $t<n$ and $r<s<m+2\le 2m+1=n$ so that from $r,s\in S$, we get $u:=r^2+s^2\in S$ and then with $t\in S$, also $n=\sqrt{u-t^2}\in S$. $\square$
