Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers 2

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|improve this answer
add comment

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|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
add comment

Your Answer

 
discard

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.