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?
Either include A or exclude A.  2 possibilities.

Either include B or exclude B.  2 possibilities.

Either include C or exclude C.  2 possibilities.

Either include D or exclude D.  2 possibilities.

So the answer is $2\times2\times2\times2$.
Its not necessay that evey number has total subsequence is equal to 2^n.
For e.g: number 12345 has following subsequence equal to 25 only. 2^n are number of subsets...
--> 1 2 3 4 5
--> 12 13 14 15 23 24 25 34 35 45
--> 123 124 125 234 235 345
--> 1234 1235 1245 1345 2345
--> 12345