I have $R$ represents a set of binary strings. also $y \times z$ represents the concatenation of strings $y$ and $z$. So if $y = 010$ and $z = 001$ then $y \times z = 010001$. I need to prove that for any string in $R$ of length $\geq 0$ in the form $p = y \times z$, I can express $y$ and $z$ such that the number of 0's in $y$ is the same as the number of 1's in $z$
For Base case $n=0$ its trivially true as both $y$ and $z$ are empty and have $0$ $0$'s and $0$ $1$'s.
From there I was thinking of assuming it applies for $n = k+1$ and showing that it would then work for $n =k$ as a result.
Not sure if this is the correct logic or if I'm doing something wrong.
Best Answer
It seems that this can be shown in a straightforward manner.
Suppose you start by splitting such that $y$ is empty, and $z=R$. Let $y_0$ track the number of $0$'s in $y$ (currently $0$) and $z_1$ the number of 1's in $z$ (starts at some number $I\geq 0$).
Now repeatedly shift the division one to the right. If the currently leftmost digit in $z$ is a 0, $y_0$ increases by 1; else it's a 1, and $z_1$ decreases by one. Either way, $z_1 - y_0$ is initially $I$ and decreases by 1 each step; eventually (namely, after exactly $I$ steps) it must reach 0, which is the desired split.