Fat Subsets

Let $S_n$ = {1, 2,...,n}.

Let $A_n$ denote the set of all $fat$ subsets of $S_n$ that contain no two consecutive integers.

Let $B_n$ denote the set of all subsets of $S_n$ in which any two elements differ by at least three.

Then $a_n$ = I $A_n$ | and $b_n$ = I $B_n$ |.

Let $C_n$ be the set of those fat subsets in $A_n$ that contain n, and let $c_n$ = I $C_n$ |.

Let s be an element of $B_n$ . If n is not in s, then s is an element of $B_{n-1}$ . If n is in s, then n-1 and n-2 are not in s, and the set s-{n} is an element of $B_{n-3}$ . Thus, $b_n = b_{n-1} + b_{n-3}$ .

Now let s be an element of $A_n$ . If n is not in s, then s is an element of $A_{n-1}$ . If n is in s, then s is in $C_n$ . Hence $a_n = a_{n-1} + c_n$ . We will show that $c_n = a_{n-3}$ by defining a bijection between $C_n$ and $A_{n-3}$ .

For an element c in $C_n$ , we map c to a as c = { $n_1 < n_2 < . . .< n_i < n$ } $-->$ a ={ $n_1-1 < n_2-1 < . . .< n_i-1$ } for i>0 and c = {n} $-->$ a = $null set$ . From the fact that $n_i < n-1$ we have n_1-1 < n-2 . From $n_1 > i$ (because c has i + 1 elements) we know that $n_1-1 > i-1$ . Hence a belongs to $A_{n-3}$ . It is then easy to check that this is indeed a bijection. The result follows by strong induction that $a_n=b_n$ for all n>0.