Something bizarre with this... Assume $f$ is such that $f(1)=1$, $f(2)=3$ and $f(k)=k$ for $k\ge 3$. This clearly enjoys the given condition that $\{k:f(k)<k\}$ is finite. Now, take $g(k)=k+1$. In this case for $k\ge 3$, $g(f(k))=g(k)=k+1$, for which the set $\{k:g(f(k))\le k\}$ is actually finite. I checked the version on http://www.imomath.com. That version asks to prove $\{k:g(f(k))\ge k\}$ is infinite. But this, again, is false. Keep as above, let $g(1)=1$ and for $k\ge 2$, $g(k)=k-1$. Then for $k\ge 3$, $g(f(k))=g(k)=k-1$, thus the given set does not contain any $k\ge 3$.. Quite strange.. Guys, let me know if you spot any mistakes in my reasoning above.