[Math] 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.

discrete mathematicsrecurrence-relations

I am trying to do two things.

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

  2. 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.

Best Answer

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:

  1. Either placing a 1 in available n places (because you can't place it at the end)
  2. or by placing a zero in available n+1 places.

So, I guess you can write the recursion now

Related Question