# 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 (Problems • Answer Key • Resources) Preceded byProblem 8 Followed byProblem 10 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 All UNCO Math Contest Problems and Solutions