Prove each nonzero integer may be uniquely represented

[jsi]

Homework Statement

prove that each nonzero integer may be uniquely represented in the form e₀ + e₁3¹ + e₂3² + ... + e_k-1e^k-1 + e_k3^k where e_k =/= 0 and each e_k = -1, 0, or 1.

Homework Equations

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 e_k = -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]

 

[jedishrfu]

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.

 

[jsi]

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...

 

[jsi]

If anyone has any other ideas, I'm really lost on this... :(

 

[Deveno]

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(10²) + (-1)

694 = 7(10²) + (-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 = 221₃ = 2(3²) + 2(3) + 1.

so to make the "200" part, we'll have to go to the next power, which is 3³, 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?)

 

[jsi]

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?

 

[Deveno]

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 (3^k), 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:

222₃ = 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).

 

[jsi]

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...

 

[jedishrfu]

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.