Number of nonempty subsets $A \subset \{1,...,n\}$ such that the smallest element of $A$ is equal to the number of elements in $A$ Let $g_n$ denote the number of nonempty subsets $A \subset \{1,...,n\}$ such that the
smallest element of $A$ is equal to the number of elements in $A$. For example, if
$n = 5$, then the possible subsets A are: $\{1\}, \{2, 3\}, \{2, 4\}, \{2, 5\}, \{3, 4, 5\}$. Find and prove a recurrence for $g_n$.
Simply by writing out all the cases, it's clear that the recurrence is
$$g_n=g_{n-1}+g_{n-2}$$
but I cannot end a proof thereof. It's pretty clear that all $g_{n-1}$ subsets in the $n-1$ case are included in the total number of subsets of the $n$ case, but I cannot find a bijection between the number of additional subsets and $g_{n-2}$. Any help to do so and/or direction for a different approach to this proof would be amazing!
 A: If a subset of $\{1,\ldots,n\}$ has $k$ elements and its smallest element is $k$, then it is of the form $\{k\}\cup S$, where $S$ is a subset of $\{k+1,\ldots,n\}$ of $k-1$ elements. Conversely, for every $k$ and  every $S\subset\{k+1,\ldots,n\}$ of $k-1$ elements the set $\{k\}\cup S$ has $k$ elements and its smallest element is $k$. So
$$g_n=\sum_{k=1}^n\binom{n-k}{k-1}.$$
You could interpret this as a $0$-th order recurrence, which is a bit contrived, or choose wisely some recurrence for binomial coefficients, and then fabricate that into a $1$-st order recurrence for $g_n$.
A: We have $g_n = g_{n-1}+g_{n-2}$.
Proof:
Out of the subsets of $\{1,2,\dots,n\}$ clearly there are $g_{n-1}$ subsets that don't contain $n$.
We now show there are $g_{n-2}$ subsets that do. In order to do this consider the following transformation: Given a subset that contains $n$ we remove $n$ and reduce every element by $1$. This gives us a valid set as long as the set doesn't contain $1$ (but it can't contain $1$ and $n$ at the same time). Conversely we can also take a subset of $\{1,2,\dots,n-2\}$ that works and increase everything by $1$ and add the element $n$. We have given a bijection between both families.
Thus there are $g_{n-1}$ that don't contain $n$ and $g_{n-2}$ that do.
A: There are $g_{n-2}$ subsets with the specified property on $[n-2]$. Now given such a set, add one onto each elements of the set and then union the element $n$. This will give the bijection.
