"Fat" sets of integers and Fibonacci numbers

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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