Solution to How many subsets of the set {1, 2, 3, 4, 5, 6, 7, 8} do … - Sikademy
Author Image

Archangel Macsika

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

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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


Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-1377-qpid-1115