I am just unsure if I did this question right and would just like to check.
Question: A bit-string is simply a finite sequence of zeroes and ones. For the purposes of this problem, strings will always have length $\ge 1$, i.e. no zero-length strings.
Let $A_n$ be the number of strings of length $n$ that have no two consecutive zeros. Thus $A_1=2$ and $A_2=3$ (strings $01$, $10$ and $11$).
Give recursive definitions for $A_n$.
My Answer(s): $$A(n+1) = A(n)+A(n-1),$$ $$A(n) = A(n-1)+A(n-2).$$
Seems true. I assume $A_n$ to be the actual sets not just their respective size. $A_{n+2}$ equals the disjoint union of the set $X$ of sequences ending in $1$ and the set $Y$ of sequences ending in $10$. $A_{n+1}$ maps bijectively on $X$ via $(x_1,\ldots,x_{n+1})\mapsto(x_1,\ldots,x_{n+1},1)$ and $A_{n}$ on $Y$ via $(x_1,\ldots,x_n)\mapsto(x_1,\ldots,x_n,1,0)$.