Write a recursive definition for the set of all binary strings that contain an odd number of zeros, and for all that end with a 0. I am trying to do two things.


*

*Write a recursive definition for the set of all binary strings with an odd number of $0$s.

*Write a recursive definition for the set of all binary strings that end with a $0$.
For my basis case for $1$ I have:
$0\in P,10\in P$
I am not sure if the second part is necessary, as I am not quite sure what I would do for the recursive step.
The second one seems easier but I am still having trouble.
Basis case:
$0\in P$
Recursive step:
If $x\in P$, then $1x\in P$ and $0x\in P$, where $0x$ and $1x$ are just concatenations of the binary strings. I believe this works but would like some verification if possible.
 A: if you have a binary string with 2n+1 number of zeros, then you can get a binary string with 2n(+1)+1 = 2n+3 number of zeros either by adding 2 zeros or 2 1's at any of the available 2n+2 positions. Way of making each of these two choices are (2n+2)$^{2}$.
So, basically if b$_{2n+1}$ is the number of binary string with 2n+1 zeros then your
b$_{2n+3}$ = 2 (2n+2)$^{2}$ b$_{2n+1}$ 
your second case is basically the fact that if you have string of length n ending with zero than you can the string of length n+1 ending with zero by:


*

*Either placing a 1 in available n places (because you can't place it at the end) 

*or by placing a zero in available n+1 places. 


So, I guess you can write the recursion now
A: *

*the second is right, no need to replicate.

*the first is:
0 $\epsilon$ P
x $\epsilon$ P $\rightarrow$ 1x $\epsilon$ P , x1 $\epsilon$ P
x'  $\epsilon$ P,x'' $\epsilon$ P $\rightarrow$ xx'x''$\epsilon$ P 


*

*important note: the difinition i offered was based on a fact P is binary string, means the leading consecutive zeros does count.

