Induct on $ m$. The case $ m = 1$ is trivial. Now prove true for $ m$ given true for $ m-1$. For all positive integers $ x > 1$, $ f(x)-f(x-1)$ equals 2 when $ x$ is a square and 1 otherwise. Suppose that the sequence $ f^{n}(m)$ does not contain a square. It then follows that $ f^{n}(m)-f^{n}(m-1) = 1$ for all $ n$. Now there exists $ N$ such that $ f^{N}(m-1) = a^{2}$ for some positive integer $ a$. We then get \[ f^{N+1}(m-1)=a^{2}+a,\ f^{N+2}(m-1)=a^{2}+2a,\] \[ f^{N+2}(m)=a^{2}+2a+1=(a+1)^{2}\] a contradiction, as desired.

Largely empirically I found the following facts (see what you can prove and note that all letters denote positive integers, unless stated otherwise): 1) The base units for the sequence $m, f(m), f(f(m)), ..$ are such that $m = n^2 + n - 1$. That is, if $m$ is not of that form, it occurs somewhere in the sequence $f(m'), f(f(m')), ..$ for some $m'$ smaller than $m$. So we can focus our attention on those base units; set $m = n^2 + n - 1$ for the remainder. 2) The smallest $x$ such that $x^2$ occurs in the sequence is equal to $2n - 1$ and occurs after $2n - 2$ steps; $f^{2n-2}(m) = (2n - 1)^2 = x^2$ 3) $y^2$ occurs in the sequence if, and only if, $y = x2^l$ for some $l \ge 0$ 4) If $f^k(m) = 4^lx^2$, then $f^{2k+2n+1-l}(m) = 4^{l+1}x^2$