We characterize the equivalence of single-input, single-output, discrete-time nonlinear systems to linear ones, via a state coordinate change and with or without feedback. Four cases are distinguished by allowing or disallowing feedback as well as by including the output map or not; the interdependence of these problems is analyzed. An important feature which distinguishes these discrete-time problems from the corresponding problem in continuous-time is that the state coordinate transformation is here directly computable as a higher composition of the system and output maps.