# How many positive integers $<1{,}000{,}000{,}000$ consist of 1's and 2's only?

My understanding is that there are 9 "places" to be filled-in with 1's and 2's and the numbers $111{,}111{,}111$ and $222{,}222{,}222$ should be discarded.

Hence my answer is $2^9 -2$ but the book says $2^{10}-2$. What am I missing?

• Why should $000,000,000$ be discarded? Did you include it in your count of $2^9$? And why should $111,111,111$ be discarded? Aug 8, 2017 at 9:13
• You forgot about numbers 1122,1221,112 Aug 8, 2017 at 9:13
• My apologies. I meant 111,111,111 and 222,222,222 should be discarded. As far as I understood the number must have both 1's and 2's. I'm I right? Aug 8, 2017 at 9:24

I don't understand why you're discarding 111,111,111 (or counting 000,000,000 in the first place).

There are $2^9$ $9$-digit numbers consisting only of $1$s and $2$s, but then you need to include the $8$-digit numbers (of which there are $2^8$), and so on down to the $1$-digit numbers. What do you get when you add all those possibilities up?

• Due to the fact he wrote 000,000,000 instead of 0, I'm confused as to whether a number such as 000,121,212 would count as per his example. The book's answer agrees with you, however. Aug 8, 2017 at 9:23
• Ah now I see. I was mistakenly discarding numbers such as 000,121,212. Aug 8, 2017 at 9:49

Let

$f(n)::=$ the number of positive integers, of which the length is equal to n, and consisting of 1's and 2's only.

What you want is $f(1)+f(2)+\cdots+f(9)$.

Then,

$$f(1)=2$$

because only $1,2$ is legal.

$$f(2) = 2f(1)$$

Then,

$$f(n)=2f(n-1)=2^2f(n-2)=\cdots=2^{n}$$

Therefore, the answer should be $2^{10}-2$.

Thanks for pointing out my mistakes by @Jaap Scherphuis and @Evargalo.

• This is wrong. Your $f(n)$ counts numbers of any length up to n, but you can only extend the ones of exactly length $n$ to length $n+1$. Your recursion should really be $f(n) = 2(f(n-1)-f(n-2)) + f(n-1)$, but it is easier to just count those of length exactly $n$. Aug 8, 2017 at 9:31
• The recurrence rule is not valid. From the number $12$, smaller than $10^3$, you're building the number $2012$, smaller than $10^4$ but that doesn't fit the exercise. Aug 8, 2017 at 9:31
• @JaapScherphuis Yes, you are right. Aug 8, 2017 at 9:39