Number of n-bit binary string with exactly 1 pair of 0s

Question

Can anyone give me a non-recursive expression for the number of length-n binary strings that have exactly one pair of consecutive 0s? I have been working on this question for hours and still have no clue.

Answer 1

Suppose we have an $n-1$-bit string with exactly $k$ $0$'s, no two of which are consecutive. We can convert this into an $n-bit$ string with exactly one pair of consecutive $0$'s by doubling any one of the $k$ $0$'s. That is, it gives rise to $k$ strings of the sort we want to count.

So, how many $n-1$-bit strings have exactly $k$ $0$'s, with no two consecutive? There are $n-1-k$ $1$'s, so there are $n-k$ places we can put the $0$'s and we can choose them in ${n-k\choose k}$ ways. Therefore, there are $k{n-k\choose k}$ $n$-bit strings with exactly one pairs of consecutive $0$'s and $k+1$ $0$'s overall.

Can you take it from here?