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?

  • $\begingroup$ 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? $\endgroup$ Aug 8, 2017 at 9:13
  • 1
    $\begingroup$ You forgot about numbers 1122,1221,112 $\endgroup$
    – TStancek
    Aug 8, 2017 at 9:13
  • $\begingroup$ 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? $\endgroup$
    – utobi
    Aug 8, 2017 at 9:24

2 Answers 2


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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – LloydTao
    Aug 8, 2017 at 9:23
  • $\begingroup$ Ah now I see. I was mistakenly discarding numbers such as 000,121,212. $\endgroup$
    – utobi
    Aug 8, 2017 at 9:49


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



because only $1,2$ is legal.

Then (think about it :),

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



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

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

  • 2
    $\begingroup$ 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$. $\endgroup$ Aug 8, 2017 at 9:31
  • 2
    $\begingroup$ 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. $\endgroup$
    – Evargalo
    Aug 8, 2017 at 9:31
  • $\begingroup$ @JaapScherphuis Yes, you are right. $\endgroup$ Aug 8, 2017 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.