Help with exercise: Binary pattern generating rule

Question

I'm having some trouble in trying to crack the logic behind this pattern. Up to binary 7 (111) I can see that the '1' holds the positions that can be occupied by moving from right to left. However, it becomes increasingly complex and can't see the pattern, specially from 10000 onwards. I've 'cheated' and used a decimal>binary conversion chart, however, I still don't see a clear pattern in the movements of the 1s. Exercise as appears in the book

Thanks in advance.

PS. The source is Geldand's Algebra.

Answer 1

Each position from right to left is a power of $2$ using conventions $m_j$ meaning $m$(base)j and $n^k$ meaning $n$(to the power of)$k$.

So $1_2=2^0=1_{10}\quad 10_2=2^1=2_{10}\quad 100_2=2^2=4_{10}$ and so on. Using this pattern we can see that $11_2=2_{10}+1_{10}=3_{10}\qquad 110_2=4_{10}+2_{10}=6_{10}\qquad 111_2=4_{10}+2_{10}=1_{10}=7_{10}.$

In the example $10000$, the $1$ is in position $5$ so, letting $p=$position, we have $10000_2=2^{p-1}=2^{5-1}=2^4=16_{10}$

Now, let's take the sequence you showed from the last number $1100=2^3+2^2=8_{10}+4_{10}=12_{10}$

The next number is simply $1100_2+1_2=1101_2=13_{10}$

The number after that has to move the rightmost $1$ to the left and leave $0$ in the last position because of a binary carry. (Think how, in base $10,\quad 9+1=10$). So we have $1101_2+1_2=1110_2=14_{10}.$ Likewise, $1110_2+1_2=1111_2=15_{10}.$

Now pay attention:$\quad 1111_2+1_2=10000_2=16_{10}\quad $ because all of the digits had to carry.

You can figure this stuff out by hand, in most cases because the numbers are small.

Example: $10101=2^4+2^2+2^0=16_{10}+4_{10}+1_{10}=21_{10}$

Answer 2

Not giving any chance to a cheat you can simply understand what it meant to be binary. So for a known number system a.k.a ' decimal number system ' we have 10 unique numbers and the numbers above 10 can be formulated using 1-10 numbers, regarding 10 as base . Likely in 'binary' system we have just two numbers 0,1 and we have to formulate every number by them and we will call them " the numbers having base 2" . And the meaning of it is more clear in the case conversion.

Supposed you have decimal number and you wanna make it binary. So u can proceed in a way that first you write it in a form $2^{n}$+p for the highest $n\in\Bbb{N}$ . And then go for long drive with p and break it in the manner. And continue it untill u see 1 at the end . For an example, Let's have 37. And we want to break it by 2 . So, here it will be like

37= $2^{5}$ +5,

5= $2^{2}$+1. And we will stop here . So resembling it all we get,

37= $2^{5}$ + $2^{2}$ +1

Now , comes the next part . As we have broken down a decimal and it looks like , `$2^{p}+2^{q}+.....+1$ . Thus we can proceed further assuming it a polynomial of degree p . And if 'D' is the decimal number then , f(x)=D is the polynomial equation whose root is 2 . And if we just collect it's coefficients and order them we will get a binary transportation. For example, we have the number 73 . And

73= $2^{6}$+ $2^{3}$+1 And , thus it can be written as , 73= $2^{6}$+ 0× $2^{5}$ + 0×$2^{4}$ +1× $2^{3}$+0× $2^{2}$+0×$2^{1}$+1× $2^{0}$`

And it is a polynomial equation of degree 6 . And as it is mentioned, the binary number (transformed) will be $1001001_{2}$ .

Now ,if you have a binary number which u have to transform into decimal , then just count how many 1 and 0 s are there , and then subtracting 1 from them , u get the order of the polynomial and the work is over . For an example if the number is ,`$100101_{2}$

Thus there is a polynomials of degree 5 and thus the decimal number will be ,

$2^{5}$+0×$2^{4}$+0×$2^{3}$+1×$2^{2}$ +0×$2^{1}$+1×$2^{0}$ i.e 37.

And u got it ! Just remember a binary number can't be started with 0 as it violates the condition of having a ' fix' degree of a polynomial.