Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.

share|cite|improve this answer

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\}$.
share|cite|improve this answer
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}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.