Proving 0s never exceed 1s in sequences without consecutive 0s

  • Context: Undergrad 
  • Thread starter Thread starter leden
  • Start date Start date
  • Tags Tags
    Induction Stuck
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
2 replies · 2K views
leden
Messages
7
Reaction score
0
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.
 

Discussion

Mathematics news on Phys.org
Try strong induction and break the string of length k into fragments.
 
If a string with more 0's then 1's is possible, there has to be a smallest string.
It must have a length at least 3, because 1, 10 and 11 are the only possible smaller strings, and they don't have more 0's then ones

This string can't have the form x1, because x would also have more 0s then 1s, so it must end in a 0.

The string can't end with 2 zero's because no consecutive 0's are allowed, so the string must have the form x10. If x10 has more zero's then ones, then so has x, which isn't possible, because x was the smallest string with more zeros then ones.