Any integer = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + + a_n

[s3a]

Homework Statement

Problem:
Prove that every positive integer P can be expressed uniquely in the form P = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + . . . + a_n where the coefficients a_i are either 0 or 1.

Solution:
Dividing P by 2, we have P/2 = a_0 * 2^(n – 1) + a_1 * 2^(n – 2) + . . . + a_(n – 1) + a_n / 2.

Then a_n is the remainder, 0 or 1, obtained when P is divided by 2 and is unique.

Let P_1 be the integer part of P/2. Then P_1 = a_0 * 2^(n – 1) + a_1 * 2^(n – 2) + . . . + a_(n – 1).

Dividing P_1 by 2, we see that a_(n – 1) is the remainder, 0 or 1, obtained when P_1 is divided by 2 and is unique.

By continuing in this manner, all the coefficients a_i can be determined to be 0 or 1 and are unique.

The problem and solution are also being made available via the attached TheProblemAndSolution.jpg file.

Homework Equations

[1] P = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + . . . + a_n where the coefficients a_i are either 0 or 1

[2] P_1 = a_0 * 2^(n – 1) + a_1 * 2^(n – 2) + . . . + a_(n – 1)

The Attempt at a Solution

The fact that any positive integer can be written in the form

P = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + . . . + a_n where the coefficients a_i are either 0 or 1

does makes sense to me.

What I don't understand is:
(i) Assuming all the coefficients a_i are remainders from division by 2, then it makes sense to me that the coefficients a_i can be 0 or 1, because when dividing by 2, those are the only two possible remainders. But, how do we determine that the coefficients a_i are remainders of division in the first place? Aren't they dividends (instead of remainders)?
(ii) What is meant by unique coefficients? If unique means that they're all different from one another, that seems impossible to me if there is at least three terms in the summation because there are only two possible values for each of the coefficients of those terms.

Any input would be greatly appreciated!

Edit:
P.S.
For what it's worth, the title should have said positive integer instead of any integer. Actually, it seems to me that 0 can also be expressed that way, so perhaps "nonnegative" (integer) would be the best terminology?

 

[verty]

Homework Statement

Problem:
Prove that every positive integer P can be expressed uniquely in the form P = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + . . . + a_n where the coefficients a_i are either 0 or 1.

Solution:
Dividing P by 2, we have P/2 = a_0 * 2^(n – 1) + a_1 * 2^(n – 2) + . . . + a_(n – 1) + a_n / 2.

Then a_n is the remainder, 0 or 1, obtained when P is divided by 2 and is unique.

Let P_1 be the integer part of P/2. Then P_1 = a_0 * 2^(n – 1) + a_1 * 2^(n – 2) + . . . + a_(n – 1).

Dividing P_1 by 2, we see that a_(n – 1) is the remainder, 0 or 1, obtained when P_1 is divided by 2 and is unique.

By continuing in this manner, all the coefficients a_i can be determined to be 0 or 1 and are unique.

The problem and solution are also being made available via the attached TheProblemAndSolution.jpg file.

Homework Equations

[1] P = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + . . . + a_n where the coefficients a_i are either 0 or 1

[2] P_1 = a_0 * 2^(n – 1) + a_1 * 2^(n – 2) + . . . + a_(n – 1)

The Attempt at a Solution

The fact that any positive integer can be written in the form

P = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + . . . + a_n where the coefficients a_i are either 0 or 1

does makes sense to me.

What I don't understand is:
(i) Assuming all the coefficients a_i are remainders from division by 2, then it makes sense to me that the coefficients a_i can be 0 or 1, because when dividing by 2, those are the only two possible remainders. But, how do we determine that the coefficients a_i are remainders of division in the first place? Aren't they dividends (instead of remainders)?
(ii) What is meant by unique coefficients? If unique means that they're all different from one another, that seems impossible to me if there is at least three terms in the summation because there are only two possible values for each of the coefficients of those terms.

Any input would be greatly appreciated!

Edit:
P.S.
For what it's worth, the title should have said positive integer instead of any integer. Actually, it seems to me that 0 can also be expressed that way, so perhaps "nonnegative" (integer) would be the best terminology?

1) They need to be 0 or 1 for it to be a unique representation. So it's better to think of them as remainders. The point is, we want a unique representation using base 2 (dividing by 2) so they must be remainders for that to happen, they can't be larger numbers.

2) Unique means that each coefficient must have the value that it has in the solution, no other solution exists.

 

[s3a]

Thanks for the reply.

After having reviewed everything that was said, I think that the proof should be reworded as follows (and please tell me if my rewording is 100% correct).:

Proof request:
Prove that every positive integer P can be expressed uniquely in the form P = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + . . . + a_n where the coefficients a_i (where i ∈ ℤ | i ≥ 0) are either 0 or 1.

Proof solution:
Let the coefficients a_i be any integers (Edit: Prior to editing, this used to say "any nonnegative integers" instead of "any integers", but I now realize that being nonnegative is not a requirement that's necessary to state, because all the coefficients a_i will be forced to be 0 or 1 anyways, so I removed the "nonnegative" adjective) such that any positive integer P can be uniquely represented as

P = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + . . . + a_n.

Dividing both sides of the equation above by 2, the following equation is obtained.:
P/2 = a_0 * 2^(n – 1) + a_1 * 2^(n – 2) + . . . + a_(n – 1) + a_n / 2

If P is even, then P/2 is an integer and a_n must equal 0.

Otherwise, if P is odd, then P/2 is an integer plus 1/2, implying that a_n must equal 1.

Let P_1 be the integer part of P/2. Then P_1 = a_0 * 2^(n – 1) + a_1 * 2^(n – 2) + . . . + a_(n – 1).

If P_1 is even, then (P_1)/2 is an integer and a_(n – 1) must equal 0.

Otherwise, if P_1 is odd, then (P_1)/2 is an integer plus 1/2, implying that a_(n – 1) must equal 1.

By continuing in this manner, all the coefficients a_i can be determined to be uniquely 0 or 1.

Furthermore, if all coefficients a_i are unique, then P must also be unique.

Therefore, every positive integer P can be expressed uniquely in the form P = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + . . . + a_n where the coefficients a_i are either 0 or 1.

 

[verty]

There is a problem, a_n could equal 2 (let P = 2 for example).

 

[s3a]

Just to make sure that I didn't miss anything, the solution of the book also has that flaw, right?

Assuming that the solution of the book also has that flaw, would a solution to that problem be to simply state that a_i ≠ P ∀ i ∈ ℤ | i ≥ 1 in the proof request (because if one of the coefficients a_i is equal in value to P and all the other coefficients a_i are 0, then that's a trivial solution)? Or does that still not address every potential issue?

 

[s3a]

Edit:
Sorry, I double-posted.

 

[s3a]

Actually, it appears that simply stating that a_i ≠ P ∀ i ∈ ℤ | i ≥ 1 in the proof request is not enough, since, for example, if P = 8, a_(n – 1) = 3, a_n = 2 and the other coefficients a_i all equal 0, it follows that

P/2 = a_0 * 2^(n – 1) + a_1 * 2^(n – 2) + . . . + a_(n – 1) + a_n / 2

implies that

8/2 = 0 + 3 + 2 / 2.

I can't find a way to rectify this problem, so could you please help me out in doing so?

 

[verty]

The problem was that you said that the coefficients must be 0 or 1 for it to work out, but that isn't true. But IF the coefficients are 0 or 1 only, then it is unique. And that is what you must show, that when they are 0 or 1, it is unique.

 

[s3a]

Okay, so in other words, I do exactly what I did, except I let all coefficients a_i be only either 0 or 1 instead of any integers, right from the start of the proof?

 

[s3a]

Just in case what I said in my previous post didn't make sense, what I meant was that the proof should

(1) assume that all coefficients are 0 or 1 from the very beginning,

(2) show that each coefficient a_i has to be strictly one of the two options 0 or 1 and it has to always be that one option (instead of a certain coefficient a_i being able to be 0 sometimes and 1 in other situations) and

(3) acknowledge that each coefficient a_i being fixed (not by choice of whoever is doing the proof – but by the laws of mathematics – i.e. if a number is even and is divided by 2, its remainder is 0, otherwise, if it's odd and is divided by 2, its remainder is 1) to strictly one of the two options (0 or 1) for a certain value of P implies that every positive integer P can be expressed uniquely in the form P = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + . . . + a_n (where the coefficients a_i are either 0 or 1).

That is what you meant by your last post, and what I should do, right?

P.S.
Sorry if I'm being repetitive; I like to reiterate what people tell me to make sure I understand, because if I don't, my lack of understanding gets noticed (which is what I want).