4 Una palabra de longitud $n$ que consiste solo en los dígitos $0$ y $1$ se denomina cadena de bits de longitud $n$ . (Por ejemplo, $000$ y $01101$ son cadenas de bits de longitud 3 y 5.) Considere la sucesión $s(1), s(2), ...$ de cadenas de bits de longitud $n > 1$ que se obtiene de la siguiente manera : (1) $s(1)$ es la cadena de bits $00...01$ , que consiste en $n - 1$ ceros y un $1$ ; (2) $s(k+1)$ se obtiene de la siguiente manera : (a) Elimine el dígito de la izquierda de $s(k)$ . Esto da una cadena de bits $t$ de longitud $n - 1$ . (b) Examine si la cadena de bits $t1$ (de longitud $n$ , añadiendo un $1$ después de $t$ ) ya está en $\{s(1), s(2), ..., s(k)\}$ . Si este no es el caso, entonces $s(k+1) = t1$ . Si este es el caso, entonces $s(k+1) = t0$ . Por ejemplo, si $n = 3$ obtenemos : $s(1) = 001 \rightarrow s(2) = 011 \rightarrow s(3) = 111 \rightarrow s(4) = 110 \rightarrow s(5) = 101$ $\rightarrow s(6) = 010 \rightarrow s(7) = 100 \rightarrow s(8) = 000 \rightarrow s(9) = 001 \rightarrow ...$ Suponga $N = 2^n$ . Demuestre que las cadenas de bits $s(1), s(2), ..., s(N)$ de longitud $n$ son todas distintas.