Why is the number of possible subsequences $2^n$? If anyone here is familiar with the Lowest Common Subsequence problem, they probably know that the number of posibble subsequences in a sequence is $2^n$; $n$ being the length of the sequence.
Another way of phrasing the statement is: given the sample space $\{a,b,c,d\}$, there are $2^4 = 16$ possible events (each event being defined as a subset of the whole sample space). 
I know it sounds a fairly basic question, but can anybody please explain why is this so?

Let us take as an example a somewhat larger problem, with a sample space of $6$ rather than your $4$.  Bhaskara, more than $800$ years ago, posed and solved a similar problem.  There are $6$ basic flavours, sweet, sour, salty, bitter, pungent, and astringent.  How many different combinations of flavours are possible?
Let us imagine that bowls of these flavouring ingredients are lined up in front of a cook. Call the bowls A, B, C, D, E, and F.  
The cook wants to create a combination of flavours by taking a tablespoon of flavouring ingredient out of some (possibly all, possibly none) of the bowls, and not using the remaining flavouring ingredients.  So (s)he stops in front of each bowl, going from left to right, and makes a decision.
Let us summarize what the cook chooses to do by using a $6$-letter word over the alphabet that consists of the "letters" $0$ and $1$. 
For example, $011001$ will mean that the cook did not use ingredient A, used B and C, did not use D and E, but used F.
It should be clear that there are exactly as many ways to choose a combination of flavourings as there are "words" of length $6$ over the alphabet $\{0,1\}$. You may already know that there are $2^6$ such words. But let us look at things from the viewpoint of the cook.
The cook stops briefly in front of bowl A. The cook has $2$ choices as to what to do: use A or not use A.  For each such choice, the cook has $2$ choices about whether to use flavour B.  For every choice about what to do with A and B, the cook has $2$ choices about what to do about C. And so on.
Thus in total the cook has 
$$2\times 2\times 2\times 2  \times 2 \times 2$$
ways of deciding about the flavourings.
This is $2^6$, or $64$.  Actually, Bhaskara got an answer of $63$, for he did not count the possibility of saying no to each flavouring, that is, of choosing the empty set of flavourings.  I guess he had not heard about English cooking.
