$\displaystyle \text{The induction step is: First, assume the inductive hypothesis: } f(n) = n.$

$\displaystyle \text{Next ASSUME, gearing for a contradiction, that } f(n+1) = f(n).$

$\displaystyle \text{Consider a no-bad-rectangle coloring of } S_{n+1} \text{ in } f(n+1) = f(n) = n \text{ colors.}$

$\displaystyle \text{On } S_{n+1} \text{ consider the } y=n+1 \text{ top horizontal row.}$

$\displaystyle \text{That row must be colored using an infinite number of some color, say green.}$

$\displaystyle \text{We'll hereafter restrict our attention only to those countable number of x such that }$

$\displaystyle \phi(x, n+1) = \text{ green.}$

$\displaystyle \text{If, on } S_n, \phi \text{ used green only a finite number of times, then discard those x's, and will have}$

$\displaystyle \text{and infinite number of x such that } \phi \text{ colors } S_n \text{ without using any green.}$

$\displaystyle \text{But now that's a coloring in } n-1 \text{ colors over an infinite subset of } \mathbb{Z}, \text{ and so could've been}$

$\displaystyle \text{used to construct an } n-1 \text{ coloring of } S_n, \text{ contrary to } f(n) = n.$

$\displaystyle \text{Therefore, on } S_n, \phi \text{ uses green for an infinite number of x.}$

$\displaystyle \text{(Note that that infinity isn't even counting the top horizontal row of } S_{n+1} \text{ that's colored infinitely often in green.}$

$\displaystyle \text{Thus one of the n rows of } S_{n} \text{ must have an infinite number of green coloring.}$

$\displaystyle \text{In particular one such row has at least 2 colorings in green.}$

$\displaystyle \text{Since that reasoning is done after restricting ourselves to only those x's where the n+1 row is colored green,}$

$\displaystyle \text{we get that those two green colorings form a bad green rectangle, which is a contradiction.}$

$\displaystyle \text{Thus the assumption }f(n+1) = f(n) \text{ has produced a contradiction.} $

$\displaystyle \text{By the initial observation, it follows that } f(n+1) = f(n)+1 = n+1.$

$\displaystyle \text{This proves that } f(n) = n \text{ implies that } f(n+1) = n+1.$

$\displaystyle \text{And, with } f(2)=2, f(3) = 3 \text{ established, that completes the proof by induction.}$