How many subsets of {1, 2, 3, 4..... 12} can be formed such that no two…

Approach: Let A(n) be the number of subsets of {1, 2, ..., n} in which no two selected elements are consecutive.

• Do not include n: then the subset can be any valid subset of {1, 2, ..., n − 1}, giving A(n − 1) choices.

• Include n: then n − 1 cannot be included, so the remaining elements come from {1, 2, ..., n − 2}, giving A(n − 2) choices.

Therefore, A(n) = A(n − 1) + A(n − 2). This is the Fibonacci recurrence.

Base cases: A(0) = 1 for the empty set, and A(1) = 2 for {} and {1}.

Values up to n = 12: A(2)=3, A(3)=5, A(4)=8, A(5)=13, A(6)=21, A(7)=34, A(8)=55, A(9)=89, A(10)=144, A(11)=233, A(12)=377.

Answer: 377