<s>[INST] "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.
 [/INST] 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.
</s>