Suppose you are building a sequence consisting of 0 and 1 in such a way that: - you start with 1 - no consecutive 0s are allowed Examples of such sequences are: 1, 1010, 110111101 etc. Empty sequence is also allowed. I want to prove by induction that the number of 0s in such a sequence is never greater than the number of 1s. (Btw, I managed to prove that the length of such a sequence is at least the number of 1s inside, but I am not sure that the proof for this is any similar to this one.) I tried almost every form of induction I could think of (except nested induction), but simply couldn't prove it. Please help.