Count all positive integers less than 100000 with at least two consecutive 1s? Okay, aforementioned was the problem:
We need to count all the positive integers with at least two consecutive ones.
The way I thought about it was:
There are $10^{5}$ ways to have numbers that are less than 100 000. Now from these, I need to subtract the number of numbers which have either no consecutive ones or one pair of consecutive ones. And we can do that by saying:
Number of no consecutive ones: ....
But this doesn't work. How to think about the problem in a easy way?Can someone help?
 A: Exactly 2 1's?
What is the number of 5 digit numbers with 2 1's?
$1^2\cdot9^3\cdot{5\choose 2}$
How many of those have the 2 1's next to each other?  How many locations are there for the first 1?
$1^2\cdot9^3\cdot{4\choose 1}$
3 ones
$1^3\cdot9^2\cdot{5\choose 3}$
And one of ${5\choose 3}$ has the 1's all separated by an intervening digit.
$1^3\cdot 9^2\cdot({5\choose 3}-1)$
4 1's and 5 1's
$1^4*9^1*{5\choose 4}$ and $1^5*9^0*{5\choose 5},$ respectively.
$4\cdot 9^3 + 9\cdot 9^2 + 5\cdot 9 + 1 = 3691$
A: It's not too hard to recursively enumerate strings of $n$ digits (allowing leading zeroes) with no consecutive ones.  Let $A_n$ be the number of such strings ending in $1$, and $B_n$ be the number ending in any other digit.  Note that a string of $n$ digits ending in $1$ can only be legally extended to a string of $n+1$ digits not ending in $1$, and that can be done in nine ways.  And a string of $n$ digits not ending in $1$ can be legally extended to a string of $n+1$ digits not ending in $1$ in nine ways, or to a string of $n+1$ digits ending in $1$ in one way.  That is,
$$
\begin{eqnarray}
A_{n+1} &=& B_n \\
B_{n+1} &=& 9B_n+9A_n.
\end{eqnarray}
$$
Starting with $A_1=1$ and $B_1=9$, it's easy enough to iterate these relations to obtain $A_5=8829$ and $B_5=87480$; so there are $A_5+B_5=96309$ numbers less than $100000$ with no consecutive ones, and $3691$ with consecutive ones.
This approach has the virtue that it leads to a closed-form, exact solution... you can find an explicit expression for $(A_n, B_n)$ using the fact that iterating a linear relation with constant coefficients is equivalent to raising the matrix of coefficients to the $(n-1)$-th power.
A: There's another way to think about it, think of numbers as words and their digits as letters, then it's the same question as asking how many words are there formed by 10 distinct letters with length exactly 6 that have two consecutive on them. (The number 11 is represented as 000011 uniquely for example)
Now put the ones in and think of how the other letters are to be put together.
A: You can always do it in the long way. Count number of numbers of each of the following form:
11, 11-, -11, 11--, -11-, --11, 11---, -11--, --11-, ---11.
