"Fat" sets of integers and Fibonacci numbers Let us call a set of integers "fat" if each of its elements is at least as large as its cardinality. For example, the set $\{10,4,5\}$ is fat, $\{1,562,13,2\}$ is not.
Define $f(n)$ to count the number of fat sets of a set of integers $\{1...n\}$ where we count the empty set as a fat set.
eg: $f(4) = 8$ because $\{Ø, \{1\}, \{2\}, \{3\}, \{4\}, \{2,3\}, \{2,4\}, \{3,4\}\}$ 
Show that $f(n) = F_{n+2}$ where $F_n$ is the nth fibonacci number. (So for $n=4, f(4)=F_6=8$).
I was given a hint to first construct a recursive equation of $f(n)$ then use the initial condition to infer that the recursive equation has to be a fibonacci recurrence thus arriving at our goal. My main guess at the recursive equation was $f(n) = f(n-1)+f(n-2)$. As to how I arrived at this, I kind of cheated by assuming the identity to be true then split $F_{n+2} = F_{n+1} + F_{n}$ and applied the identity.
I want to show that this recurrence is true (which I guess is done by induction in some form or even better, a combinatorics argument as the structure looks rather familiar) then the rest I'm sure will follow given initial conditions.
Any advice in the right direction would be greatly appreciated.

This problem has a simple solution using ordinary generating functions.
Observe that the generating function  of subsets of $\{k, n\}$ indexed
by number of elements ($u$) and  total sum ($x$) is by inspection seen
to be
$$\prod_{m=k}^n (1+ux^m).$$
Therefore the generating function of the sets being considered is
$$\sum_{k=0}^n [u^k] \prod_{m=k}^n (1+ux^m)$$
where $[u^k]$ is the coefficient extraction operator.
For our purposes we don't  need the sum parameter from this generating
function so we may set it to one, getting
$$\sum_{k=0}^n [u^k] \prod_{m=k}^n (1+u)
= \sum_{k=0}^n [u^k] (1+u)^{n-k+1}
= \sum_{k=0}^n {n-k+1\choose k}.$$
We will now compute the generating function $f(z)$ of this sum, getting
$$f(z) = \sum_{n\ge 0} z^n \sum_{k=0}^n {n-k+1\choose k}
= \sum_{k\ge 0} \sum_{n\ge k} {n-k+1\choose k} z^n
= \sum_{k\ge 0} \sum_{n\ge 0} {n+1\choose k} z^{n+k}
\\= \frac{1}{1-z} + 
\sum_{k\ge 1} \sum_{n\ge 0} {n+1\choose k} z^{n+k}
= \frac{1}{1-z} + 
\sum_{k\ge 1} \sum_{n\ge k-1} {n+1\choose k} z^{n+k}
\\= \frac{1}{1-z} + 
\sum_{k\ge 1} \sum_{n\ge 0} {n+k\choose k} z^{n+2k-1}
= \frac{1}{1-z} + 
\sum_{k\ge 1} z^{2k-1} \sum_{n\ge 0} {n+k\choose k} z^n
\\= \frac{1}{1-z} + 
\sum_{k\ge 1} z^{2k-1} \frac{1}{(1-z)^{k+1}}
= \frac{1}{1-z} + \frac{1}{1-z} \frac{1}{z}
\sum_{k\ge 1} z^{2k} \frac{1}{(1-z)^k}
\\ = \frac{1}{1-z} + \frac{1}{1-z} \frac{1}{z}
\frac{z^2/(1-z)}{1-z^2/(1-z)}
= \frac{1}{1-z} + \frac{1}{1-z} \frac{1}{z}
\frac{z^2}{1-z-z^2}.$$
This finally simplifies to
$$\frac{1}{1-z}
\left(1 + \frac{z}{1-z-z^2}\right)
= \frac{1}{1-z} \frac{1-z-z^2 + z}{1-z-z^2}
= \frac{1+z}{1-z-z^2}.$$
Now recall that the generating function of the Fibonacci numbers is
given by $$\frac{z}{1-z-z^2}$$ and therefore
$$[z^n] \frac{1+z}{1-z-z^2}
= F_{n+1} + F_n = F_{n+2}.$$
Addendum. An alternate evaluation of the OGF proceeds as follows:
$$f(z) =
\sum_{n\ge 0} z^n [w^{n+1}] (1+w)^{n+1}
\sum_{k\ge 0}
\frac{w^{2k}}{(1+w)^k}
\\ = \frac{1}{z}
\sum_{n\ge 0} z^{n+1} [w^{n+1}] (1+w)^{n+1}
\frac{1}{1-w^2/(1+w)}
\\ = \frac{1}{z}
\sum_{n\ge 0} z^{n+1} [w^{n+1}] (1+w)^{n+2}
\frac{1}{1+w-w^2}.$$
The contribution from $w$ is
$$\;\underset{w}{\mathrm{res}}\;
\frac{1}{w^{n+2}} (1+w)^{n+2} \frac{1}{1+w-w^2}.$$
Now put $w/(1+w)=v$ so that $w = v/(1-v)$ and $dw = 1/(1-v)^2 \; dv$ to
get
$$\;\underset{v}{\mathrm{res}}\;
\frac{1}{v^{n+2}} \frac{1}{1+v/(1-v)-v^2/(1-v)^2} \frac{1}{(1-v)^2}.$$
This gives for the OGF
$$\frac{1}{z} \sum_{n\ge 0} z^{n+1} [v^{n+1}]
\frac{1}{(1-v)^2+v(1-v)-v^2}
\\ = \frac{1}{z} \sum_{n\ge 0} z^{n+1} [v^{n+1}]
\frac{1}{1-v-v^2}
= \frac{1}{z} \left[ -1 + \frac{1}{1-z-z^2} \right]
\\ = \frac{1}{z} \frac{z+z^2}{1-z-z^2}
= \frac{1+z}{1-z-z^2},$$
the same as before.
