Proving the uniqueness of Binary Integer Representations

shaoen01 · 2008-02-23 04:23:24

Hi all,

I am having some problems understanding how to prove the uniqueness of Binary Integer Representations and i hope someone can help me try to understand it better.

Qns:
Given any positive integer n, n has a unique representation in the form of

where r is a nonnegative integer,

Given Solution:
I was told to suppose that there is an integer n with two different representations as a sum of nonnegative integer powers of 2. Equating the two representations and canceling all identical terms gives:

where r and s are nonnegative integers, r<s and each and each equal 0 or 1. But by the formula for the sum of a geometric sequence:

which contradicts "

". Hence, the supposition is false, so any integer n has only one representations as a sum of nonnegative integer powers of 2.
[/math]

What i don't understand:
What does this statement mean exactly "integer n with two different representations as a sum of nonnegative integer powers of 2"? How do we derive

? And why is there a contradiction? I do not understand how the inequality equation was formed.

JaneFairfax · 2008-02-23 06:07:05

Thats not the whole solution; thats only part of it.

Okay, a little terminology to explain things better. When you write n as

where r is the largest non-negative integer such that c[sub]r[/sub] = 1, r is called the degree of the representation. What you have shown is that if you can write n as two representations, then the degrees of the two representations must be identical. You have not shown that the two represntations themselves must be identical!

This is how to complete the uniqueness proof.

Since the RHS has degree 0, so must the LHS, i.e. c[sub]i[/sub] = d[sub]i[/sub] for all i=0,1,,r.

Note also that show that a representation is unique still does not prove that a representation is possible at all. You still need to show that every integer can have such a representation. Here is a sketch proof.

By the division algorithm,

where 0 ≤ s[sub]r[/sub] < 2[sup]r[/sup] and 2[sup]r[/sup] is the largest power of 2 not greater than n. Note that

Now apply the same division algorithm to s[sub]r[/sub] and a lesser power of 2. Continuing this way, n will eventually be laid out as a linear combination of powers of 2 with coefficients 0 or 1.

Last edited by JaneFairfax (2008-02-23 12:29:02)

Ricky · 2008-02-23 10:11:22

Equivalent statement:

Let B = {2^0, 2^1, 2^2, ...}. Prove that the vector space of integers modulo 2 over B has no subspace B' such that span(B') = Z.

shaoen01 · 2008-02-23 20:36:59

Hi JaneFairFax:

I am sorry but i didn't quite understood this line from your reply:

. I do not get what "n>=2^r"? I don't think i have touched the division algorithm yet, the only division theorem i know is n=dq + r --> Is that the same?

Ricky: I am sorry, i didn't manage to catch your explanation.

All: I have just started on basic discrete mathematics, so please be patient with me. Thanks!

Ricky · 2008-02-24 05:11:03

Ricky: I am sorry, i didn't manage to catch your explanation.

It wasn't an explanation, but rather restating your question using different (algebraic) words.

John E. Franklin · 2008-02-24 18:44:08

Show that to find a second way to the number you have to
break rules, such as breaking borders created by using only
one or zero, but the 2 (not allowed) in a place, then jumps
into the next zone, twice as far...

Math Is Fun Forum

#1 2008-02-23 04:23:24

Proving the uniqueness of Binary Integer Representations

#2 2008-02-23 06:07:05

Re: Proving the uniqueness of Binary Integer Representations

#3 2008-02-23 10:11:22

Re: Proving the uniqueness of Binary Integer Representations

#4 2008-02-23 20:36:59

Re: Proving the uniqueness of Binary Integer Representations

#5 2008-02-24 05:11:03

Re: Proving the uniqueness of Binary Integer Representations

#6 2008-02-24 18:44:08

Re: Proving the uniqueness of Binary Integer Representations

Board footer