1. The problem statement, all variables and given/known data
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.
2. Relevant 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)
3. 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?
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.
2. Relevant 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)
3. 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?
0 commentaires:
Enregistrer un commentaire