Discrete time non-linear time invariant system dynamics descriptions (state-space or input-output relationship)
Well, any input-output representation obviously admits a state-sapce form. for your equation in $y[k]$ you can easily construct one as follows. Create a "shift" system (an integrator chain) as
$$
\begin{aligned}
x_1[k+1] &amp;= x_2[k],\\
x_2[k+1] &amp;= x_3[k],\\
&amp;\vdots\\
x_n[k+1] &amp;= y[k]
\end{aligned}
$$
In this way indeed you have $x_n[k] = y[k-1]$, $x_{n-1}[k]=y[k-2]$, ..., $x_1[k] = y[k-n]$. You can do the same by defining another shift system to carry the information in $u[k]$, namely
$$
\begin{aligned}
z_1[k+1] &amp;= z_2[k],\\
z_2[k+1] &amp;= z_3[k],\\
&amp;\vdots\\
z_m[k+1] &amp;= u[k]
\end{aligned}
$$
Thus, with $\xi := col(x_1,...,n_n,z_1,...,z_m)$ the IO representation is equivalent to
$$
\begin{aligned}
\xi[k+1] &amp;= A\xi[k],\\
y[k] &amp;= h(\xi_1[k],\dots,\xi_n[k],u[k],\xi_1[k],\dots,\xi_m[k])
\end{aligned}
$$
The converse is instead not trivial. Pick the LTI system
$$
\begin{aligned}
x[k+1] &amp;= \begin{bmatrix}2 &amp; -1\\0 &amp; 0.1\end{bmatrix}x[k] + \begin{bmatrix}1\\1\end{bmatrix}u[k],\qquad (1)\\
y[k] &amp;= x_2[k]
\end{aligned}
$$
Then the output is the same as
$$
y[k] = 0.1 y[k-1] + u[k],\qquad (2)
$$
however, (2) and (1) are not equivalent. 
In general, given a IO representation you can always find a state-space representation, however for general state-space forms a IO representation might be not enough to describe the whole state information. You should find a diffeomorphism among the two representations to assess equivalence