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$
$\endgroup$
3
-
$\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$– This site has become a dump.Aug 8, 2017 at 9:13
-
1$\begingroup$ You forgot about numbers 1122,1221,112 $\endgroup$– TStancekAug 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$– utobiAug 8, 2017 at 9:24
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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?
answered Aug 8, 2017 at 9:14
-
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$– LloydTaoAug 8, 2017 at 9:23
-
$\begingroup$ Ah now I see. I was mistakenly discarding numbers such as 000,121,212. $\endgroup$– utobiAug 8, 2017 at 9:49
$\begingroup$
$\endgroup$
3
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.
-
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$– EvargaloAug 8, 2017 at 9:31
-