2018 UNCO Math Contest II Problems/Problem 9

Problem

Call a set of integers Grassilian if each of its elements is at least as large as the number of elements in the set. For example, the three-element set $\{2, 48, 100\}$ is not Grassilian, but the six-element set $\{6, 10, 11, 20, 33, 39\}$ is Grassilian. Let $G(n)$ be the number of Grassilian subsets of $\{1, 2, 3, ..., n\}$. (By definition, the empty set is a subset of every set and is Grassilian.)

(a) Find $G(3)$, $G(4)$, and $G(5)$.

(b) Find a recursion formula for $G(n + 1)$. That is, find a formula that expresses $G(n + 1)$ in terms of $G(n), G(n - 1),\dots$

(c) Give an explanation that shows that the formula you give is correct.

Solution

a) $G(3) = 5, G(4) = 8, G(5) = 13$

b) $G(n) = G(n - 1) + G(n - 2); G(0) = 1 \text{ and } G(1) = 2$

c) $G(n + 1) = G(n) + G(n - 1)$.

See also

2018 UNCO Math Contest II (ProblemsAnswer KeyResources)
Preceded by
Problem 8
Followed by
Problem 10
1 2 3 4 5 6 7 8 9 10
All UNCO Math Contest Problems and Solutions