"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.
 A: HINT: Notice that every fat subset of $\{1,\dots,n\}$ is automatically a fat subset of $\{1,\dots,n+1\}$; that accounts for $f(n)$ fat subsets of $\{1,\dots,n+1\}$, so you just need to show that there are $f(n-1)$ fat subsets of $\{1,\dots,n+1\}$ that are not already fat subsets of $\{1,\dots,n\}$. Clearly those must be the fat subsets of $\{1,\dots,n+1\}$ that include $n+1$. At this point it might not be a bad idea to collect some data by listing the fat subsets of $\{1,\dots,n\}$ for some small values of $n$:
$$\begin{array}{c|l}
n&\text{Fat subsets}\\ \hline
0&\varnothing\\
1&\varnothing,\{1\}\\
2&\varnothing,\{1\},\{2\}\\
3&\varnothing,\{1\},\{2\},\{3\},\{2,3\}\\
4&\varnothing,\{1\},\{2\},\{3\},\{2,3\},\{4\},\{2,4\},\{3,4\}\\
5&\varnothing,\{1\},\{2\},\{3\},\{2,3\},\{4\},\{2,4\},\{3,4\},\{5\},\{2,5\},\{3,5\},\{4,5\},\{3,4,5\}
\end{array}$$
Now try to match up the new sets on each line with the sets two lines back:
$$\begin{array}{c|l|c|l}
n&\text{Fat subsets}&n+2&\text{New fat subsets}\\ \hline
0&\varnothing&2&\{2\}\\
1&\varnothing,\{1\}&3&\{3\},\{2,3\}\\
2&\varnothing,\{1\},\{2\}&4&\{4\},\{2,4\},\{3,4\}\\
3&\varnothing,\{1\},\{2\},\{3\},\{2,3\}&5&\{5\},\{2,5\},\{3,5\},\{4,5\},\{3,4,5\}\\
\end{array}$$
If you stare at that table for a bit, you should be able to see how to derive the new fat subsets of $\{1,\dots,n+1\}$, the ones that aren’t fat subsets of $\{1,\dots,n\}$, from the fat subsets of $\{1,\dots,n-1\}$. Once you see it, proving that it’s correct isn’t too hard.
A: 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.
A: Hint: I would do this by justifying the following three claims.


*

*A fat subset of $\{1,2,\ldots,n-1\}$ is also a fat subset of $\{1,2,\ldots,n\}$.

*If $X$ is a fat subset of $\{1,2,\ldots,n-2\}$, then the set
$$
X_+=\{n\}\cup\{t+1\mid t\in X\} 
$$
is a fat subset of $\{1,2,\ldots,n\}$.

*If a fat subset $S\subseteq\{1,2,\ldots,n\}$ satisfies $n\in S$, then $S=X_+$ for
some fat subset $X$ of $\{1,2,\ldots,n-2\}$.

