# How many Binary numbers?

How many binary numbers of length $n$ can be generated where $n > 7$ and the number either start with $000$ or end with $111$?

My questions is, can I choose an $n$ randomly? For example, let's say that $n = 8$. Since the first three terms need to be $0$, they can have only one option and the remaining five digits can be $0$s or $1$s meaning that they have two options. The same identity applies for the ending with $111$ case.

So my guess is, $2^5+2^5 = 32+32 = 64$

Is this answer correct? By the way forgive me if I couldn't explained my answer clearly, thanks..

• you forgot to take into consideration, that n>7... – V-X Oct 13 '14 at 19:35
• I did not forget, i chose 8 as n. What do do you mean by that, couldn't see your point :) – odd Oct 13 '14 at 19:36
• You have counted the numbers of form $000xy111$ twice. – Antoine Oct 13 '14 at 19:36
• Use the fact that $|A\cup B|=|A|+|B|-|A\cap B|$ – Peter Franek Oct 13 '14 at 19:38
• The answer should be given as a function of $n$. – barak manos Oct 13 '14 at 19:40

there is $$2^{n-3}$$ numbers of length n with 000 at the beginning and there is $$2^{n-3}$$ numbers of length n with 111 at the end. also there is $$2^{n-6}$$ numbers that has both 000 at the beginning and 111 at the end, thus the result is $$2 * 2^{n-3} - 2^{n-6} = 15 * 2^{n-6}$$ numbers corresponding your conditions...
The amount of $n$-digit numbers that start with $000$ is $2^{n-3}$
The amount of $n$-digit numbers that end with $111$ is $2^{n-3}$
The amount of $n$-digit numbers that start with $000$ and end with $111$ is $2^{n-6}$
The amount of $n$-digit numbers that start with $000$ or end with $111$ is $2^{n-3}+2^{n-3}-2^{n-6}$