- #1
leden
- 7
- 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.
- 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.