1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove each nonzero integer may be uniquely represented

  1. Jan 19, 2012 #1

    jsi

    User Avatar

    1. The problem statement, all variables and given/known data

    prove that each nonzero integer may be uniquely represented in the form e0 + e131 + e232 + ... + ek-1ek-1 + ek3k where ek =/= 0 and each ek = -1, 0, or 1.

    2. Relevant equations



    3. The attempt at a solution

    I feel like this has to do with the basis representation theorem because it's in that section of my textbook. It looks to me like one would be able to represent the integers in base 3 since that's basically what it's saying but that would be only obvious for the positive integers and I'm not sure how to solve for that, or where the ek = -1 would come in... any help would be appreciated, thanks!

    [edit]

    I did out for the first few integers, 1,...6 or so and found
    if n=1 e_0 = 1 => 1 = 1
    if n=2 e_0 = -1 and e_1 = 1 => -1 + 3(1) = 2
    if n=3 e_0 = 0 and e_1 = 1 => 0 + 3(1) = 3
    if n=4 e_0 = 1 and e_1 = 1 => 1 + 3(1) = 4
    if n=5 e_0 = -1 and e_1 = -1 and e_2 = 1 => -1 + 3(-1) + 3*3(1) = 5
    if n=6 e_0 = 0 and e_1 = -1 and e_2 = 1 => 0 + 3(-1) + 3*3(1) = 6

    so there seems to be the pattern that e_0 goes 1, -1, 0 for each successive n and maybe e_1 goes 1,1,1,-1,-1,-1(?) for each successive n after n=1. I'm not sure where to go with this except that it seems to show something of a pattern, I just don't understand how to go about proving it.
    [/edit]
     
    Last edited: Jan 19, 2012
  2. jcsd
  3. Jan 19, 2012 #2

    jedishrfu

    Staff: Mentor

    yeah that's an interesting pattern

    1x 1 -1 0 1 -1 0 1 -1 0 ...
    3x 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 0 0 0 ...
    9x 0 0 0 0 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 ...
    1 2 3 4 5 6 7 8 9

    binary counting has a similar pattern:

    1x 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 e0
    2x 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 e1
    4x 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 e2
    8x 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 e3

    and -1 in binary is: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 (16-bit)
    ^
    ^
    ^ < < < sign bit when 0 its positive when 1 its negative

    you might be able to prove it via induction you'd have to figure out a rule that when adding 1
    to a term that is ONE means it becomes a -1 and then a ONE must added to the next higher term
    unless its a ONE which it too becomes a -1 and then a ONE must be added to the next higher term...
    like binary carry over.
     
  4. Jan 19, 2012 #3

    jsi

    User Avatar

    I'm not really sure how what you said relates... I need some sort of push or hint in the right direction from what I discovered with the pattern I outlined...
     
  5. Jan 22, 2012 #4

    jsi

    User Avatar

    If anyone has any other ideas, I'm really lost on this... :(
     
  6. Jan 22, 2012 #5

    Deveno

    User Avatar
    Science Advisor

    ok, we can convert a number to base 3, right?

    to do this, we use the digits 0,1 and 2 (notice that we use just 3 digits, and we're in base 3...hmm....)

    now, can you think of a clever way to use -1 and 1 (times various powers of 3) instead of the digit "2"?

    (hint: in base 10, we don't actually need the digit 9, if we can use -1:

    99 = 1(102) + (-1)

    694 = 7(102) + (-1)(10) + 4,

    see what i'm getting at?)

    in other words, to avoid using the digit 2, use 1 in leading digits (higher powers of 3) until you go just PAST the number you are trying to total to, and then subtract powers of 3 until you get lower.

    for example, here is 25:

    25 = 2213 = 2(32) + 2(3) + 1.

    so to make the "200" part, we'll have to go to the next power, which is 33, or 27. but this is "too big", so we need to subtract 3 in the "3's place" (the difference is < 9, so we don't need to add anything as big as nine).

    1,0,0,0 --> 1,0,-1,0....now we are too small (27 - 3 = 24), so we need to add a 1 in the "1's place":

    1,0,-1, 0 ---> 1,0,-1,1, and "reverse the order"

    25 = 1(1) + (-1)(3) + 0(9) + 1(27) +......all zeros after.

    so, to prove the general case, you need to show that you can always "keeping moving the problem (the 2 digit), to a lesser power of 3".

    essentially, you may wind up "zig-zagging" around the target number, and what you want to do is prove that the "amount you miss by" (with each successive "zig" or "zag") keeps getting smaller, and is eventually 0 (your induction "base" case will involve showing that for numbers < 3, we have:

    0 = 0
    1 = 1
    2 = ...?)

    (note that although this only show it for non-negative integers, the negative integer case should follow soon after. why?)
     
  7. Jan 22, 2012 #6

    jsi

    User Avatar

    thank you! I guess I understand all that and the numerical manipulation and everything, I just don't know where to begin on how to prove it because it seems like there are many cases to prove, like if it's -1, 0, or 1, and then if the number is negative with it having -1, 0, or 1? And I get that you can represent 2 as (3-1) which would be 3^1 - 1(3^0) but then that just makes me think you'd need to put that in everywhere you need a 2 if you were to do it strictly in base 3 and then how would you go about proving for a representation that had multiple 2s that needed to be replaced because then all the other numbers in the representation would be moved around... Maybe I'm just way overthinking about it in the wrong way or something?
     
  8. Jan 22, 2012 #7

    Deveno

    User Avatar
    Science Advisor

    well let's say a base 3 representation had a whole slew of 2's.

    all you need to show is that if a 2 is in the k-th place (3k), you can replace it by an expression (using just 1, and -1 and 0 in the k-th place or higher) in which the possible 2's get "kicked down to lesser digits", and use induction.

    if we have a number between 18 and 26, for example, which would be 2AB, for digits A and B in the set {0,1,2},

    we can write 18 (20 in base 3) as 27-9, so that is:

    1,-1,0,0 + something (where "something" is less than 9).

    now if A = 0 or 1, when we add whatever number AB represents in base 3, the "power of 3 place" will be either -1, or 0. then it doesn't matter what "B" is, we "moved the possible 2's downstairs", so we repeat the process (at most adding 1 in "the next higher power from B (if B = 2, it might cause the correction from A to change the 2nd digit in our 1,0,-1 form to 1, which is OK).

    the only problem might be if A = 2. because then B matters. because if B = 2 as well, converting IT to -1,0, and 1 form, might cause an extra one in the (former) A's place, but this never happens:

    2223 = 26, start with 26 = 27-9 (18) + something (which is 8, 22 in base 3):

    1,-1,0,0 + something (the AB part). A = 2 --> 1,-1,0 (6 in our system), add them:

    1,-1,0,0
    0,1,-1,0
    --------
    1,0,-1,0 <---so far this is just 24

    now you can see that converting the last digit (B, which is 2) might affect the next-to-the last place, but it can't "get to" the digit before that: 2 = 1,-1, and adding this:

    1,0,-1,0
    0,0,1,-1
    --------
    1,0,0,-1 <--- finally, 26.

    do you see what's happening? if we have a "2 digit" we turn that into a 1 and -1 pair, and the -1 is "further down" (a lesser power of 3), so we don't have to worry about somehow "a carried one" turning our 1's "upstream" back into 2's (the -1 stops this from happening).
     
  9. Jan 22, 2012 #8

    jsi

    User Avatar

    thank you for your well explained responses! I do see what's happening and I understand what you're explaining because it's in terms of specific examples and that all makes sense. Again, I really am lost as to how to prove it... I know you say prove if there's a 2 in the k place show you can change it into what the problem gives, I really just have no idea of how to go about doing that... and even once that is shown, I still have to show that the whole problem works, not just that that part of it works...
     
  10. Jan 22, 2012 #9

    jedishrfu

    Staff: Mentor

    You need to do an induction proof:

    Step 1 prove for one number

    Step 2 assume it works for k and prove for k+1 this is the tricky part for this example

    Try this and show some work we need to see work before we can help anymore.

    You need to try before we reply.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook