# “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.

-
That's cheating. $f(n) = f(n-1) + f(n-2)$ is not the only recurrence relation that generates Fibonacci numbers, e.g. $f(n) = 2f(n-2) + f(n-3)$ would work too. – dtldarek Mar 14 '13 at 7:40

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.

-

Hint: I would do this by justifying the following three claims.

1. A fat subset of $\{1,2,\ldots,n-1\}$ is also a fat subset of $\{1,2,\ldots,n\}$.
2. 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\}$.
3. 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\}$.
-
Your example with $n=4$ already suggests this. There are the five fat subsets of $\{1,2,3\}$, and three fat subsets containing number $4$ as an element such that the remaining elements of those subsets are gotten by adding $1$ to all the elements of a fat subset of $\{1,2\}$. – Jyrki Lahtonen Mar 14 '13 at 7:51

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}.$$

-