Amount of binary number without the sequence '01'

Question

Assume we have a number $n$. How many binary numbers exists with exactly $n$ digits and without the sequence '01'. For example 1000 is such a number an 0010 is not because it contains the sequence '01'.

I think there exists $n+1$ with this properties. Because for every $ i = 0 ...n$ there exist exactly one binary number of length $n$ with exactly i zeros in the number. Am i right ? I don't know how to formalize my thoughts ?

Answer 1

Your idea is correct. And you don't need much work to "formalize" your thoughts. Just make sure you write it in such a way that the idea comes through clearly, and you're done. To that end, I also believe you should use one or two sentences to explain why "there exist exactly one binary number of length $n$ with exactly i zeros in the number."

Also, we like to use the word "binary strings" rather than "numbers". For instance, that makes it a bit clearer that $0011$ is different from $011$.

So to formalise it, we don't really need much more than what you already have. Just add in a few extra words here and there to make the sentences clearer, and add the sentence I mentioned above, and that should be enough. Something like

There exist $n+1$ binary strings of length $n$ with no substring $01$. That is because for every $i$ from $0$ to $n$ there exists exactly one binary string without $01$ of length $n$ with exactly $i$ zeros in the number with. This follows from the fact that in any such string, all $1$s must be on the right, and all $0$s must be on the left.

is enough for me.