1. ## please explain me this counting

How many bit strings with length not exceeding n, where n is a positive integer, consist entirely of 1s?

Answer is n+1 (counting the empty string)
Where on earth the empty string comes?

2. Originally Posted by zpwnchen
How many bit strings with length not exceeding n, where n is a positive integer, consist entirely of 1s?
Answer is n+1 (counting the empty string)
Where on earth the empty string comes?
I have no idea. I think that is an absurd idea.

But that must be defined somewhere in your text material.
If so, you should use it.

3. Originally Posted by Plato
I have no idea. I think that is an absurd idea.

But that must be defined somewhere in your text material.
If so, you should use it.
I don't think the empty string is an "absurd idea" at all. Almost all programming languages that I know of have it. Also, the set of all strings, including the empty string, forms a monoid with respect to concatenation - and the empty string is the neutral element for that monoid. If we did not allow the empty string, then the set of strings would not form a monoid with respect to concatenation, which would be very sad indeed.

Once one accepts that the concept of an empty string is quite reasonable, the next question concerns the answer to the exercise in question. Now consider: are all characters contained in the empty string equal to 1? - The answer is yes, of course. Hence the empty string has to be included in the counting of all strings of length $\displaystyle \leq n$ consisting entirely of 1s.

4. ## Re: please explain me this counting

The question says that the string should not exceed length 'n' , so a null string of length 0 should be acceptable . Right ?

5. ## Re: please explain me this counting

Originally Posted by Failure
Now consider: are all characters contained in the empty string equal to 1? - The answer is yes, of course.
Personally, I find the idea of a empty string containing only 1s rather preposterous. If it is going to be considered to contain any character it should be zero. This would accord with it's boolean translation (in most languages) of False.

Having said that, the interpretation under which we say that strings consisting only of 1s are those that do not contain any 0s would give a natural case for inclusion of the empty string.