Answer to Question #250991 in Discrete Mathematics for dfgfdg

Question

How many subsets of the set {1, 2, 3, 4, 5, 6, 7, 8} do not contain two consecutive integers ?

Answer 1

Let S = {1, 2, . . . , 8} and let $S_e=\{2,4,6,8\}$ and $S_o=\{1,3,5,7\}$ .

A subset T of S has no element which are consecutive integers if and only if $T=T_o\subset T_e$ where $T_e \subset S_e$

and $T_o\subset S_o$ , such that Te has no two consecutive elements from the list 2, 4, . . . ,8 and To

contains no two consecutive elements of the list 1, 3, . . . , 7. Furthermore if an allowable

subset T of S is given, then the sets Te and To are uniquely determined, and Te and To

satisfy the stated conditions. Thus if $a_4$ is the number of ways to form a set from the

list 2, 4, 6, 8 containing no two consecutive elements, then the number of subsets of

S with no elements differing by 2 is $a_4^2$ We determine $a_4$ .

To simplify notation, let $a_n$ be the number of subsets of Sn = {1, 2, . . . , n} containing no

two consecutive element of Sn. It is easy to see that $a_1$ = 2 (we get the empty set φ and

the set {1}) and $a_2=3$ . Now suppose that n ≥ 3. If an allowable subset of Sn contains

n, then the other elements of the set can make up any allowable subset of $S_{n-2}$ . If the

allowable subset does not contain n, then the elements of the set must be an allowable

subset of $S_{n-1}$ . Thus

$a_n=F_{n+2}$ where $F_n$ denotes the $n^{th}$ Fibonacci number. (the Fibonacci numbers are

defined by $F_0=0,F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for n ≥ 2.) Thus we find that the number

of subsets of $S_8$ with no element which are consecutive integer

$a_4^2=F_{4+2}^2=F_6^2=8^2=64$