# Why the number of subsets S ⊂ {1,…,n} without an odd number of consecutive integers is F(n+1)?

I have two questions about the Fibonacci sequence:

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!

• The set containing 1 (or any single number) is a set containing an odd number of consecutive integers. – Jonny Nov 12 '14 at 19:40
• For $n=1$, $\{1\}$ is a set with an odd number of consecutive integers, since $1$ is odd. – AlexR Nov 12 '14 at 19:40
• Yes, 1 is odd, but if the set itself will contain only one item {1}, isn't that an odd number of items in the set, not an odd number of consecutive integers?, cause simply there aren't consecutive numbers to be count in order to determine if they are odd or even... It doesn't make sense to me... – user3019105 Nov 12 '14 at 20:12

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$