Keep a safe distance!

Let $A(n)$ denote the number of subsets of the set $\{1,2,\ldots, n\}$ , containing the element $n$ and satisfying the given constraint of no two consecutive elements.

Similarly let $B(n)$ denote the number of subsets of the set $\{1,2,\ldots, n\}$ , not containing the element $n$ and satisfying the given constraint of no two consecutive elements.

Our objective is to find $A(10)+B(10)$ .

Now it is easy to see that $A(n)$ and $B(n)$ satisfies the following two recursion equations

$A(n)=B(n-1)$ and $B(n)=A(n-1)+B(n-1)$ , with the initial condition $A(1)=B(1)=1$ . Using the recursion, we get $A(10)+B(10)=144$ .

Let A(n) denote the number of subsets of the set {1,2,....,n} excluding the null set phi and having no consecutive integer elements.

Now, it can be clearly seen that A(n) can be expressed as A(n-1) + A(n-2), because for each of A(n-2) subsets we can form another subset with the nth element.

This gives us a recursive relation. Add 1 in the end for null set. Gives 144.

(PS I am new to computers, please pardon my not using LaTeX.)