How many different choice of sets? If $S_1$, $S_2$, $\dots$, $S_r$ are r sets, $S_i\subseteq \{1,2,\dots,n\}$. $|S_i|\geq 1$ for all $i$ and $S_i\cap S_{i+1}$=$\emptyset$ for all $1\leq i\leq r-1$. How many different chioce of $S_1,\dots,Sr$ are there?

I have this strong feeling it has to be with Fibonnaci sequence.
As seeing in Morgan O answer, you must solve that expression. Let's see the first two. 
I am gonna call $A_{n,r}$ the numbers. So
$A_{n,1}=2^n-1$, because the only subset you are not allowed to take is $\emptyset$
$$A_{n,2} =\sum_{a_1=1}^{n-1}\binom{n}{a_1}\sum_{a_2=1}^{n-a_1}\binom{n-a_1}{a_2}=\sum_{a_1=1}^{n-1}\binom{n}{a_1}(2^{n-a_1}-1)=3^n-2^n-A_{n,1}$$
$$A_{n,3}=\sum_{a_1=1}^{n-1}\binom{n}{a_1}\sum_{a_2=1}^{n-a_1}\binom{n-a_1}{a_2}\sum_{a_3=1}^{n-a_2}\binom{n-a_2}{a_3}=5^n-3^n-2^nA_{n,1}-A_{n,2}$$
So, the guess might be $A_{n,k}=F_{k+1}^n-F_{k}^n-\sum_{i=1}^{k-1} F_{i}^nA_{n,k-i}$, where $F_i$ is the fibonacci sequence. 
And it does not seems to be very crazy because of the Binomial theorem, when you are solving the expression you are carrying a sequence of two numbers starting by 1,2 and adding them always with a residue(because the index start by 1 and not by 0, as Morgan O pointed out).
