Given a string $w \in \{1,2\}^*$, let $F(w) \in \mathbb{N}$ be the sum of all the numbers in it. For example, $F(\epsilon) = 0$ for the null string $\epsilon$, and $F(1212) = 6$. Now define some $$S_n = \{ w \in \{1,2\}^*: F(w) = n\}$$
Some examples: $\epsilon \in S_0$ and $1212 \in S_6$.
I want to find the cardinality of $S_n$ for each $n\in \mathbb{N}$ and prove this is correct.
My thoughts:
Seems like this is a question fit for induction, but I have some trouble finding the induction hypothesis, which is essentially the task of "finding the cardinality of $S_n$.
From another perspective, it seems that I can possibly using something like the CBS theorem to show the cardinality if I can find $S_n$ as bijective to some $[n]$ and then relate it to say $\#S_n = n$
How should I proceed?
Hint: a string with sum $n$ can either start with a string with sum $n-1$ to which a $1$ is added or a string with sum $n-2$ to which a $2$ is added. Compute a few terms. You should recognize the sequence.