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

Question

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?

Answer 1

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?

Answer 2

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.

Then (think about it :),

$$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.