I have two questions about the Fibonacci sequence:
I read from Wikipedia:
1) The number of subsets S ⊂ {1,...,n} without an odd number of consecutive integers is F(n+1).
2) The number of binary strings of length n without an even number of consecutive 0s or 1s is 2*Fn. For example, out of the 16 binary strings of length 4, there are 2*F4 = 6 without an even number of consecutive 0s or 1s – they are 0001, 0111, 0101, 1000, 1010, 1110. There is an equivalent statement about subsets.
Regarding subsets (not binary strings, which I understand because of the examples), why these two affirmations are to be considered true?
Let's take the first affirmation:
The number of subsets S ⊂ {1,...,n} without an odd number of consecutive integers is F(n+1).
I can suppose that this affirmation can be true for n = 0 like this:
n = 0
F(0 + 1) = F(1) = 1
S ⊂ {...empty set...}, so there's only one set -> ∅
But for n = 1
F(1 + 1) = F(2) = 1
S ⊂ {1}, but there are 2 sets, aren't they? -> ∅ and {1}
And for n = 4
F(5) = 5
S ⊂ {1,2,3,4}, there are 6 sets without an odd number of consecutive integers:
1) {1,2,3,4} -> 4 number of consecutive integers (not odd)
2) {4}
3) {3}
4) {2}
5) {1}
6) ∅
I guess I have not understand something, so please correct me!
For $n=1$, $\{1\}$ contains an odd number of consecutive integers, where the odd number is $1$.
When you have the set $\{1,2,\cdots, n\}$, you can get the recurrent relation by considering subsets satisfying the condition with or without $n$