Let $a(n)$ be the number of subsets $A$ of $\{1,2,...,n\}$ with the property that $A$ is either the empty set or $\forall k \in A ( k \geq |A|)$. How can I prove that $a(n) = F(n+2)$ and show that this also implies $\displaystyle F(n+1) = \sum_{k=0}^n \binom{n-k}{k}$?
Note: $F(n)$ are the Fibonacci numbers.
Thank you for your time!
For the first part, one can prove this by induction on $n$. Call these subsets size-dominating. Let's suppose we've checked the base cases.
Let $A$ be a size-dominating subset of $\{1,\ldots,n+1\}$. If $A$ does not contain $n$, then $A$ is also a size-dominating subset of $\{1,\ldots,n\}$, and the converse is also true (any size-dominating subset of $\{1,\ldots, n\}$ is also a size-dominating subset of $\{1,\ldots, n+1\}$); there are (by the inductive hypothesis) $F_{n+2}$ of these. On the other hand, if $A$ contains $n$, then $A$ cannot contain $1$ (since then it would contain two elements, and $2>1$). So then $A^\prime = \{x-1\ |\ x\in (A\setminus\{n\})\}$ is a size-dominating subset of $\{1, \ldots, n-1\}$ of which there are $F_{n-1}$ by the inductive hypothesis. Again, the reverse is true as well; if $A$ is a size-dominating subset of $\{1, \ldots, n-1\}$ then $\{x+1\ |\ x\in A\} \cup \{n+1\}$ is a size-dominating subset of $\{1,\ldots, n+1\}$.
This means that the number of size-dominating subsets of $\{1,\ldots, n+1\}$ is $F_{n+2} + F_{n+1} = F_{n+3}$, completing the proof by induction.
To show the last equality, observe that a size-dominating subset of $\{1,\ldots,n-1\}$ is necessarily the empty set (there are $\binom{n}{0} = 1$ of these) or, for some $1\leq k$, a subset of size $k$ of the $n-k$ numbers between $k$ and $n-1$ inclusive, of which there are $\binom{n-k}{k}$.
$a(n) = |{A \subset {1, ..., n}: A = \emptyset $ or $\forall$ $k \in A, k \geq |A|}|$
– Christopher Nov 26 '13 at 14:55