I know this might be one of the silliest questions out there but I'm going ahead and ask it here since I've lost practice in mathematics.
I have been reading that the number of subsequences in a string is $2^x$ where $x$ is the length of the string and I have also worked some examples which agree with this, however I still am not very comfortable with this explanation. Can somebody formally prove this in simple terms please? More specifically where does the $2$ come from?
In constructing a subsequence, each element may be present or absent. That gives two choices for each. As there are $x$ choices, you multiply that many $2$'s together. It is the same as finding the number of subsets of a set, the order carries over from the original sequence to the subsequence. As an example, take the sequence $1,2,3$ and try to find all the subsequences by hand. You should find $2^3=8$ of them. Each corresponds to one of the binary numbers from $000$ to $111$, where a $0$ says that element is not present in the subsequence and a $1$ says it is.