SOLUTION: Richard Stanley writes in his book "Enumerative Combinatorics" that it is easily seen why {{{f(n) = f(n-1)+f(n-2)}}} where f(n) is the number of subsets of [n] (<i>{1,2,3,..,n}</i>

Question 62971: Richard Stanley writes in his book "Enumerative Combinatorics" that it is easily seen why where f(n) is the number of subsets of [n] ({1,2,3,..,n}) that do not contain two consecutive integers.

Can someone actually explain why it is so, please?

Thanks!
Answer by joyofmath(189) (Show Source): You can put this solution on YOUR website!
Richard Stanley writes in his book "Enumerative Combinatorics" that it is easily seen why where f(n) is the number of subsets of [n] ({1,2,3,..,n}) that do not contain two consecutive integers.

Can someone actually explain why it is so, please?
This is an interesting problem that took me a while to figure out. I can give you the gist of what's going on but you'd have to do a proof, either by induction or by contradiction to really prove the relationship.
Here's the idea:
Let's enumerate the subsets when n=3: {}{1}{2}{3}{13}
Let's enumerate the subsets when n=4: {}{1}{2}{3}{4}{13}{14}{24}
Now, let's say we want to construct the subsets when n=5. We can do this as follows, in two steps:
1. Take all the subsets we used for n=4. They're all still legal when n=5.
2. Take all the subsets we used for n=3. Add the number 5 to the end of each subset. That would give us {5}{15}{25}{35}{135}.
Combining the subsets from n=3 (with the 5 tacked onto the end of each subset) and n=4 gives us the subsets for n=5 which is the motivation behind .
Note that there's no duplication between the subsets in n=3 with the 5's tacked on and the subsets in n=4 because the subsets in n=4 can't have any 5's (because n=4). Note also that tacking 5 onto the subsets in n=3 is legal since the n=3 subsets all end in 3 or less and thus tacking on 5 doesn't violate the nonconsecutive number constraint.
Does this make sense?
Note, you'd have to do a real proof, in particular you'd need to prove that no subsets were missing when we construct f(n) from f(n-1) and f(n-2).
RELATED QUESTIONS
The Fibonacci sequence, is defined by F_0 = 0, F_1 = 1, and F_n = F_{n - 2} + F_{n - 1}. (answered by CPhill,greenestamps)

f(n)=1^2+2^2+3^2+...+n^2 it turns out that f is a polynomial of degree x in n. Figure out (answered by venugopalramana)

if f ^(2 n)(x) + ((f (x) - 2))^(2 n) = x ^(2 n), n \[Element] N , then (dx)/(d (f (x)))... (answered by ikleyn)

f(n) = n^5 - n , n = N , then f(n) is divisible... (answered by Fombitz)

What is the Big O of (n/2) log(n/2) + f(n), where f(n) = o (sqrt n log^9... (answered by Alan3354)

Let {F(n)} = {1,1,2,3,5,8,13,21,34,55,��} be the Fibonacci sequence defined by F(1) = (answered by AnlytcPhil)

The function f(n) is defined for all integers n, such that f(x) + f(y) = f(x + y) -... (answered by CPhill,ikleyn)

The length of a field in yards is a function f(n) of the length n in feet. Write a... (answered by stanbon)

A function f is defined for integers m and n as given: {{{ f(mn) =... (answered by Edwin McCravy)