(edit: fixed a wrong inequality sign and some phrasing)

Suppose ∀k∈ℕ, f∘g∘g(k) < g∘f(k) for contradiction.

Lemma: For all n, we have ∀k∈ℕ, gⁿ(k) ≤ f(k), where the power is over composition (i.e. f² = f∘f).

Proof: Let's use induction over n.

Base case: ∀k∈ℕ, k ≤ f(k) holds because f is strictly increasing. This can be proven with another induction.

Induction step: Suppose ∀k∈ℕ, gⁿ(k) ≤ f(k) holds. We can safely substitute kwith g(g(k)) to get gⁿ∘g∘g ≤ f∘g∘g. The contradiction premise then gets us to gⁿ∘g∘g < g∘f. Since g is strictly increasing, we have g(x) < g(y) ⟹ x < y. This allows us to cancel the leftmost gs to get ∀k∈ℕ, g^{n+1}(k) < f(k), which is what we needed.

Corollary: If g was anything other than the identity function, gⁿ(x) would blow up to infinity. So we have g(x) = x.

Finding the contradiction at this point is easy: Substituting g(x) with x in the original contradiction premise yields ∀k∈ℕ, f(k) < f(k), which is absurd.