Finding the number of k-tuples of sets. Find the number of k-tuples of sets $<S_1,...,S_k>$ where $S_1,...,S_k ⊆$ {1,...,n} and where:
$S_1⊆S_2⊇S_3⊆S_4⊇S_5⊆S_6⊇ ...$
So I think it will look something like this: picture
 but can't figure how to find the answer.  Any ideas?
 A: The answer to your question is:
$$(F_{k+2})^n$$
    Where F is the fibbonacci function, defined as:
$$F_{n} = F_{n-1} + F_{n-2}$$
$$F_{1} = F_{2} = 1$$
The core idea behind this is that each of the n elements in {1,...,n} can be considered separately for the purpose of building the k-tuple. Then, once we have the number of k-tuples over a set of 1 element, we just raise it to the n'th power
to account for the rest of the set.
$$$$
Proof: 
For clarity, let's denote the number of such k-tuples over {1,...,n} to be f(n,k). First, we look at the special case of n=1; that is, a set of one element.
There are 2 cases:
Case 1: S_1 is empty

    This implies that there are  no restriction on what we can place in S_2. 
    This means that there f(1,k-1) sets satisfying case 1.
Case 2: S_1 contains 1

    This implies that S_2, being a superset of S_1, contains 1. This in turn 
    means that there is no restriction on S_3. Thus there are f(1,k-2) sets 
    satisfying case 2. 

Clearly Case 1 and Case 2 partition the space, and so we must have:
$$f(1,k) = f(1,k-1) + f(1,k-2)$$
Looking at some base cases and counting manually, we get that:
$$f(1,1)=2=F_3$$
$$f(1,2)=3=F_4$$
Thus, $f(1,k) = F_{k+2}$.
Moving back to general n, notice that we can break the problem into n steps: 
Choose which sets in <S_1, ... ,S_k> 1 goes into

Choose which sets in <S_1, ... ,S_k> 2 goes into

.

.

.

Choose which sets in <S_1, ... ,S_k> n goes into

Clearly, these represent independent actions. It follows then that:
$$f(n,k) = f(1,k)^n$$
Substituting our expression for f(1,k) we finally get that: 
$$f(n,k) = (F_{k+2})^n$$
