¿Cómo puedo encontrar la cardinalidad de las cadenas en este conjunto?

Question

Dada una cadena $w \in \{1,2\}^*$ , dejemos que $F(w) \in \mathbb{N}$ sea la suma de todos los números que contiene. Por ejemplo, $F(\epsilon) = 0$ para la cadena nula $\epsilon$ y $F(1212) = 6$ . Ahora define algunos $$S_n = \{ w \in \{1,2\}^*: F(w) = n\}$$

Algunos ejemplos: $\epsilon \in S_0$ y $1212 \in S_6$ .

Quiero encontrar la cardinalidad de $S_n$ para cada $n\in \mathbb{N}$ y demostrar que esto es correcto.

Mis pensamientos:

1. Parece que esta es una pregunta apta para la inducción, pero tengo algunos problemas para encontrar la hipótesis de inducción, que es esencialmente la tarea de "encontrar la cardinalidad de $S_n$ .

2. Desde otra perspectiva, parece que posiblemente pueda usar algo como el teorema CBS para mostrar la cardinalidad si puedo encontrar $S_n$ como biyectiva a alguna $[n]$ y luego relacionarlo para decir $\#S_n = n$

¿Cómo debo proceder?

Answer 1

Sugerencia: una cadena con suma $n$ puede comenzar con una cadena con suma $n-1$ a la que un $1$ o una cadena con suma $n-2$ a la que un $2$ se añade. Calcula algunos términos. Deberías reconocer la secuencia.