Mixing
Uniqueness of radix representation of integers in base 3
$begingroup$
I have recently begun self-studying Number Theory, and am working on proving:
Show that every integer $n>0$ can be uniquely written as $$n = sum_{i=0}^mc_i3^i$$ where $c_i in { -1,0,1}$ and $c_m neq 0$.
I believe I have already shown the existence portion of this proof correctly, and now I am looking for some hints on the uniqueness part. So far what I have tried is:
Suppose for the sake of contradiction that there is an alternate representation of $n$ besides $n = sum_{i=0}^mc_i3^i$, say $n = sum_{i=0}^pb_i3^i$ where we still have $b_p neq 0$ and $b_i in {-1,0,1}$.
At this point I felt that I first need to establish that $m=p$, and second show $c_i=b_i$ for each $i in {1,2,dots, m}$. To show the former, I left off in my proof by contradiction with
Without loss of generality suppose $p>m$. We know there is an integer $q$ such that $m+q=p$. We have two ways of writing $n$, which means $$ sum_{i=0}^pb_i3^i-sum_{i=0}^mc_i3^i=0 \ implies left(sum_{i=0}^mb_i3^i+sum_{i=m+1}^{m+q}b_i3^iright)-sum_{i=0}^mc_i3^i=0 \ implies sum_{i=0}^m(b_i-c_i)3^i+sum_{i=m+1}^{m+q}b_i3^i=0 \ implies sum_{i=m+1}^{m+q}b_i3^i=sum_{i=0}^m(c_i-b_i)3^i$$
At this point I am stuck. If anyone has any hints to help me find the contradiction or feel that there is a better way to establish uniqueness, please let me know!
elementary-number-theory
edited Jan 25 at 15:48
Bill Dubuque
212k29195654
asked Jan 5 '15 at 16:04
graydadgraydad
12.8k61933
$endgroup$
add a comment |
$begingroup$
I have recently begun self-studying Number Theory, and am working on proving:
Show that every integer $n>0$ can be uniquely written as $$n = sum_{i=0}^mc_i3^i$$ where $c_i in { -1,0,1}$ and $c_m neq 0$.
I believe I have already shown the existence portion of this proof correctly, and now I am looking for some hints on the uniqueness part. So far what I have tried is:
Suppose for the sake of contradiction that there is an alternate representation of $n$ besides $n = sum_{i=0}^mc_i3^i$, say $n = sum_{i=0}^pb_i3^i$ where we still have $b_p neq 0$ and $b_i in {-1,0,1}$.
At this point I felt that I first need to establish that $m=p$, and second show $c_i=b_i$ for each $i in {1,2,dots, m}$. To show the former, I left off in my proof by contradiction with
Without loss of generality suppose $p>m$. We know there is an integer $q$ such that $m+q=p$. We have two ways of writing $n$, which means $$ sum_{i=0}^pb_i3^i-sum_{i=0}^mc_i3^i=0 \ implies left(sum_{i=0}^mb_i3^i+sum_{i=m+1}^{m+q}b_i3^iright)-sum_{i=0}^mc_i3^i=0 \ implies sum_{i=0}^m(b_i-c_i)3^i+sum_{i=m+1}^{m+q}b_i3^i=0 \ implies sum_{i=m+1}^{m+q}b_i3^i=sum_{i=0}^m(c_i-b_i)3^i$$
At this point I am stuck. If anyone has any hints to help me find the contradiction or feel that there is a better way to establish uniqueness, please let me know!
elementary-number-theory
edited Jan 25 at 15:48
Bill Dubuque
212k29195654
asked Jan 5 '15 at 16:04
graydadgraydad
12.8k61933
$endgroup$
$begingroup$
Suppose $b_{m+1} = 1$. Then even if all the $c_i - b_i = 1$, maximizing the expression on the right, then that sum would still be less than $3^{m+1}$. There is a similar case for $b_{m+1} = -1$. For the case $b_{m+1} = 0$, there must be some $b_j neq 0$, $j > m+1$.
$endgroup$
– Simon S
Jan 5 '15 at 16:09
1
$begingroup$
Note that that's called "balanced ternary," whereas just "ternary" usually means base $3$ with the digits $0$, $1$, $2$. Thus, in ternary, $26$ is $222$ but in balanced ternary you'd have a $1$ followed by two $0$s and ending with a $-1$.
$endgroup$
– user153918
Jan 5 '15 at 18:26
add a comment |
$begingroup$
I have recently begun self-studying Number Theory, and am working on proving:
Show that every integer $n>0$ can be uniquely written as $$n = sum_{i=0}^mc_i3^i$$ where $c_i in { -1,0,1}$ and $c_m neq 0$.
I believe I have already shown the existence portion of this proof correctly, and now I am looking for some hints on the uniqueness part. So far what I have tried is:
Suppose for the sake of contradiction that there is an alternate representation of $n$ besides $n = sum_{i=0}^mc_i3^i$, say $n = sum_{i=0}^pb_i3^i$ where we still have $b_p neq 0$ and $b_i in {-1,0,1}$.
At this point I felt that I first need to establish that $m=p$, and second show $c_i=b_i$ for each $i in {1,2,dots, m}$. To show the former, I left off in my proof by contradiction with
Without loss of generality suppose $p>m$. We know there is an integer $q$ such that $m+q=p$. We have two ways of writing $n$, which means $$ sum_{i=0}^pb_i3^i-sum_{i=0}^mc_i3^i=0 \ implies left(sum_{i=0}^mb_i3^i+sum_{i=m+1}^{m+q}b_i3^iright)-sum_{i=0}^mc_i3^i=0 \ implies sum_{i=0}^m(b_i-c_i)3^i+sum_{i=m+1}^{m+q}b_i3^i=0 \ implies sum_{i=m+1}^{m+q}b_i3^i=sum_{i=0}^m(c_i-b_i)3^i$$
At this point I am stuck. If anyone has any hints to help me find the contradiction or feel that there is a better way to establish uniqueness, please let me know!
elementary-number-theory
edited Jan 25 at 15:48
Bill Dubuque
212k29195654
asked Jan 5 '15 at 16:04
graydadgraydad
12.8k61933
$endgroup$
I have recently begun self-studying Number Theory, and am working on proving:
Show that every integer $n>0$ can be uniquely written as $$n = sum_{i=0}^mc_i3^i$$ where $c_i in { -1,0,1}$ and $c_m neq 0$.
I believe I have already shown the existence portion of this proof correctly, and now I am looking for some hints on the uniqueness part. So far what I have tried is:
Suppose for the sake of contradiction that there is an alternate representation of $n$ besides $n = sum_{i=0}^mc_i3^i$, say $n = sum_{i=0}^pb_i3^i$ where we still have $b_p neq 0$ and $b_i in {-1,0,1}$.
At this point I felt that I first need to establish that $m=p$, and second show $c_i=b_i$ for each $i in {1,2,dots, m}$. To show the former, I left off in my proof by contradiction with
Without loss of generality suppose $p>m$. We know there is an integer $q$ such that $m+q=p$. We have two ways of writing $n$, which means $$ sum_{i=0}^pb_i3^i-sum_{i=0}^mc_i3^i=0 \ implies left(sum_{i=0}^mb_i3^i+sum_{i=m+1}^{m+q}b_i3^iright)-sum_{i=0}^mc_i3^i=0 \ implies sum_{i=0}^m(b_i-c_i)3^i+sum_{i=m+1}^{m+q}b_i3^i=0 \ implies sum_{i=m+1}^{m+q}b_i3^i=sum_{i=0}^m(c_i-b_i)3^i$$
At this point I am stuck. If anyone has any hints to help me find the contradiction or feel that there is a better way to establish uniqueness, please let me know!
elementary-number-theory
elementary-number-theory
edited Jan 25 at 15:48
Bill Dubuque
212k29195654
asked Jan 5 '15 at 16:04
graydadgraydad
12.8k61933
edited Jan 25 at 15:48
Bill Dubuque
212k29195654
asked Jan 5 '15 at 16:04
graydadgraydad
12.8k61933
edited Jan 25 at 15:48
Bill Dubuque
212k29195654
edited Jan 25 at 15:48
Bill Dubuque
212k29195654
edited Jan 25 at 15:48
Bill Dubuque
212k29195654
212k29195654
asked Jan 5 '15 at 16:04
graydadgraydad
12.8k61933
asked Jan 5 '15 at 16:04
graydadgraydad
12.8k61933
asked Jan 5 '15 at 16:04
graydadgraydad
12.8k61933
12.8k61933
$begingroup$
Suppose $b_{m+1} = 1$. Then even if all the $c_i - b_i = 1$, maximizing the expression on the right, then that sum would still be less than $3^{m+1}$. There is a similar case for $b_{m+1} = -1$. For the case $b_{m+1} = 0$, there must be some $b_j neq 0$, $j > m+1$.
$endgroup$
– Simon S
Jan 5 '15 at 16:09
1
$begingroup$
Note that that's called "balanced ternary," whereas just "ternary" usually means base $3$ with the digits $0$, $1$, $2$. Thus, in ternary, $26$ is $222$ but in balanced ternary you'd have a $1$ followed by two $0$s and ending with a $-1$.
$endgroup$
– user153918
Jan 5 '15 at 18:26
add a comment |
$begingroup$
Suppose $b_{m+1} = 1$. Then even if all the $c_i - b_i = 1$, maximizing the expression on the right, then that sum would still be less than $3^{m+1}$. There is a similar case for $b_{m+1} = -1$. For the case $b_{m+1} = 0$, there must be some $b_j neq 0$, $j > m+1$.
$endgroup$
– Simon S
Jan 5 '15 at 16:09
1
$begingroup$
Note that that's called "balanced ternary," whereas just "ternary" usually means base $3$ with the digits $0$, $1$, $2$. Thus, in ternary, $26$ is $222$ but in balanced ternary you'd have a $1$ followed by two $0$s and ending with a $-1$.
$endgroup$
– user153918
Jan 5 '15 at 18:26
$begingroup$
Suppose $b_{m+1} = 1$. Then even if all the $c_i - b_i = 1$, maximizing the expression on the right, then that sum would still be less than $3^{m+1}$. There is a similar case for $b_{m+1} = -1$. For the case $b_{m+1} = 0$, there must be some $b_j neq 0$, $j > m+1$.
$endgroup$
– Simon S
Jan 5 '15 at 16:09
$begingroup$
Suppose $b_{m+1} = 1$. Then even if all the $c_i - b_i = 1$, maximizing the expression on the right, then that sum would still be less than $3^{m+1}$. There is a similar case for $b_{m+1} = -1$. For the case $b_{m+1} = 0$, there must be some $b_j neq 0$, $j > m+1$.
$endgroup$
– Simon S
Jan 5 '15 at 16:09
1
1
$begingroup$
Note that that's called "balanced ternary," whereas just "ternary" usually means base $3$ with the digits $0$, $1$, $2$. Thus, in ternary, $26$ is $222$ but in balanced ternary you'd have a $1$ followed by two $0$s and ending with a $-1$.
$endgroup$
– user153918
Jan 5 '15 at 18:26
$begingroup$
Note that that's called "balanced ternary," whereas just "ternary" usually means base $3$ with the digits $0$, $1$, $2$. Thus, in ternary, $26$ is $222$ but in balanced ternary you'd have a $1$ followed by two $0$s and ending with a $-1$.
$endgroup$
– user153918
Jan 5 '15 at 18:26
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
If you know a bit about modular arithmetic, then there is a relatively easy way to work this out (it is equivalent to the proofs already here, but perhaps is a little cleaner conceptually). Suppose that you have $x_0 = sum_{n = 0}^infty a_n 3^n = sum_{n = 0}^infty b_n 3^n$ (with the understanding that for large enough $n$, $a_n$ and $b_n$ are $0$).
Take $x_0$ modulo $3$. It is apparent that we must have $x_0 = a_0 = b_0 mod 3$, which of course implies that $a_0 = b_0$. Now, consider $x_1:=frac{x_0 - a_0}{3}$. It is an integer, so it makes sense to reduce it modulo $3$ again---this time, we get the equality $x_1 = a_1 = b_1 mod 3$, so $a_1 = b_1$. Define $x_2 := frac{x_1 - a_1}{3}$, rinse, and repeat. An easy induction proves the result.
answered Jan 6 '15 at 1:46
Arseniy SheydvasserArseniy Sheydvasser
1263
$endgroup$
$begingroup$
Thanks for breaking it down a bit more! That should help me get it all finished up :)
$endgroup$
– graydad
Jan 6 '15 at 2:51
add a comment |
$begingroup$
The best approach is to use induction.
If $sum a_i3^i = sum b_i3^i$, first show that $a_0=b_0$ and thus that:$$sum_{i>0} a_i3^{i-1} = sum_{i>0} b_i3^{i-1}$$
Then apply the induction hypothesis.
answered Jan 5 '15 at 16:10
Thomas AndrewsThomas Andrews
130k12147298
$endgroup$
$begingroup$
Thank you, I will give this a shot. Why did you subtract $1$ from $i$ in the exponent after showing $a_0=b_0$?
$endgroup$
– graydad
Jan 5 '15 at 16:28
$begingroup$
The claim you are proving by induction considers sums which range from terms starting with $3^0$.
$endgroup$
– dalastboss
Jan 6 '15 at 2:14
add a comment |
$begingroup$
Hint $ $ Viewing radix representation as a polynomial in the radix, this can be reduced to a result related to the rational root test - see the result below, which, slightly modified, also works here.
If $,g(x) = sum g_i x^i$ is a polynomial with integer coefficients $,g_i,$ such that $,0le g_i < b,$ and $,g(b) = n,$ then we call $,(g,b),$ the radix $,b,$ representation of $,n.,$ It is unique: $ $ if $,n,$ has another rep $,(h,b),,$ with $,g(x) ne h(x),,$ then $,f(x)= g(x)-h(x)ne 0,$ has root $,b,$ but all coefficients $,color{#c00}{|f_i| < b},,$ contra the following slight generalization of: $ $ integer roots of integer polynomials divide their constant term.
Theorem $ $ If $,f(x) = x^k(color{#0a0}{f_0}!+f_1 x +cdots + f_n x^n)=x^kbar f(x),$ is a polynomial with integer coefficients $,f_i,$ and with $,color{#0a0}{f_0ne 0},$ then an integer root $,bne 0,$ satisfies $,bmid f_0,,$ so $,color{#c00}{|b| le |f_0|}$
Proof $, 0 = f(b) = b^k bar f(b),overset{large b,ne, 0}Rightarrow, 0 = bar f(b),,$ so, subtracting $,f_0$ from both sides yields $$-f_0 =, b,(f_1!+f_2 b+,cdots+f_n b^{n-1}), Rightarrow,bmid f_0, overset{large color{#0a0}{f_0,ne, 0}}Rightarrow, |b| le |f_0|qquad {bf QED}qquadquad$$
answered Jan 5 '15 at 16:18
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
add a comment |
$begingroup$
Hint:
- Note that $$(3^m+3^{m-1}+ldots+1)-(-3^m-3^{m-1}-ldots-1)=3^{m+1}-1$$ since $3-1=2$ and $3^{m+1}-1=3cdot3^m-1=2cdot3^m+(3^m-1)$.
- You could strengthen your argument so that each integer from $(-3^m-ldots-1)$ to $(3^m+ldots+1)$ can be expressed.
- In such case you are representing $3^{m+1}$ possibilities with at most $3^{m+1}$ different sums, that is, you get uniqueness for almost free.
- The first bullet makes for an elegant induction hypothesis, because $$3^{m+1}+(-3^m-3^{m-1}-ldots-1) = (3^m+3^{m-1}+ldots+1)+1.$$
I hope this helps $ddotsmile$
answered Jan 5 '15 at 16:40
dtldarekdtldarek
32.5k745101
$endgroup$
$begingroup$
@graydad That was a typo, updated now.
$endgroup$
– dtldarek
Jan 5 '15 at 16:47
$begingroup$
I'm still unsure how you get the first equality. Is it $$(3^{m+1}+3^{m}+ldots+3^1)-(-3^m-3^{m-1}-ldots-3^1-1)=3^{m+1}-1$$
$endgroup$
– graydad
Jan 5 '15 at 16:48
$begingroup$
@graydad After simplifying you get $2cdot 3^m+2cdot3^{m-1}+ldots+2 = 3^{m+1}-1$, which is intuitively true because it is the highest $m$-digit number you can get in the ordinary base-3, i.e. $22222ldots222_text{base 3}$.
$endgroup$
– dtldarek
Jan 5 '15 at 16:56
$begingroup$
Ah I see it now. Thank you for explaining further. I will play around with this result :)
$endgroup$
– graydad
Jan 5 '15 at 17:06
add a comment |
$begingroup$
Outline of Proof:
1) first assume n has a representation as required
2) Show that for each representation of $n$ we can find a representation for $n-1$. This means if we know a representation for an integer greater than $n$, we can find one for $n$.
3)$3^n$ is greater than n and has a representation; therefore so does $n$
4)Squeeze the number of representations for $n$ between 1 and 1.
Suppose that n has a representation of the form $n = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0$. Now we want to subtract 1 from both sides, $n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0-1$. Now, $n-1$ does not have the proper representation yet. On its own $-1$ can be written $-1=-1*3^0$. We can now write $n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0$.
We want to say here that given a representation of $n$ satisfying the requirements we can find a representation of $n-1$ that does as well, but for the case $c_0=-1$ we get a coefficient of $-2$ for the last term.
So for the case $c_0=-1$ we will use the formula $-2*3^j=-3^{j+1}+3^j$ to rewrite $n-1$.$n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0=c_m3^m+c_{m-1}3^{m-1}+...-2*3^0=c_m3^m+c_{m-1}3^{m-1}+...-3^1+3^0$. Now we realize that there may exist a term w/ coefficient $-1$ and exponent $1$ and we are back where we started.
But, there must exist a last term with $-1$ as a coefficient. Let the kth term be the last one with coefficient $-1$, then we have $n-1=c_m3^m+c_{m-1}3^{m-1}+...-3^{k+1}+3^k+3^{k-1}+...+3^0
$ and this representation meets the requirements.
So we have shown that for each representation of $n$ we can find a representation for $n-1
$. Since $3^n>n>0$ and $3^n$ has a representation(itself) then a representation for n can be found progressively.
Uniqueness:
Let $b_k(n)$ represent the total number of representations for $n$. Since for each representation of $n$ we can find one for $n-1$ we have $b_k(n)$<=$b_k(n-1)$. (Skipping a bit) we have finally 1<=$b_k(3^n)<=b_k(n)<=b_k(1)=1$.
The total number of representations for $n$ is between $1$ and $1$ and must therefore be $1$
answered Jan 23 '15 at 3:31
Vladimir LouisVladimir Louis
1027
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1091962%2funiqueness-of-radix-representation-of-integers-in-base-3%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
If you know a bit about modular arithmetic, then there is a relatively easy way to work this out (it is equivalent to the proofs already here, but perhaps is a little cleaner conceptually). Suppose that you have $x_0 = sum_{n = 0}^infty a_n 3^n = sum_{n = 0}^infty b_n 3^n$ (with the understanding that for large enough $n$, $a_n$ and $b_n$ are $0$).
Take $x_0$ modulo $3$. It is apparent that we must have $x_0 = a_0 = b_0 mod 3$, which of course implies that $a_0 = b_0$. Now, consider $x_1:=frac{x_0 - a_0}{3}$. It is an integer, so it makes sense to reduce it modulo $3$ again---this time, we get the equality $x_1 = a_1 = b_1 mod 3$, so $a_1 = b_1$. Define $x_2 := frac{x_1 - a_1}{3}$, rinse, and repeat. An easy induction proves the result.
answered Jan 6 '15 at 1:46
Arseniy SheydvasserArseniy Sheydvasser
1263
$endgroup$
$begingroup$
Thanks for breaking it down a bit more! That should help me get it all finished up :)
$endgroup$
– graydad
Jan 6 '15 at 2:51
add a comment |
$begingroup$
If you know a bit about modular arithmetic, then there is a relatively easy way to work this out (it is equivalent to the proofs already here, but perhaps is a little cleaner conceptually). Suppose that you have $x_0 = sum_{n = 0}^infty a_n 3^n = sum_{n = 0}^infty b_n 3^n$ (with the understanding that for large enough $n$, $a_n$ and $b_n$ are $0$).
Take $x_0$ modulo $3$. It is apparent that we must have $x_0 = a_0 = b_0 mod 3$, which of course implies that $a_0 = b_0$. Now, consider $x_1:=frac{x_0 - a_0}{3}$. It is an integer, so it makes sense to reduce it modulo $3$ again---this time, we get the equality $x_1 = a_1 = b_1 mod 3$, so $a_1 = b_1$. Define $x_2 := frac{x_1 - a_1}{3}$, rinse, and repeat. An easy induction proves the result.
answered Jan 6 '15 at 1:46
Arseniy SheydvasserArseniy Sheydvasser
1263
$endgroup$
$begingroup$
Thanks for breaking it down a bit more! That should help me get it all finished up :)
$endgroup$
– graydad
Jan 6 '15 at 2:51
add a comment |
$begingroup$
If you know a bit about modular arithmetic, then there is a relatively easy way to work this out (it is equivalent to the proofs already here, but perhaps is a little cleaner conceptually). Suppose that you have $x_0 = sum_{n = 0}^infty a_n 3^n = sum_{n = 0}^infty b_n 3^n$ (with the understanding that for large enough $n$, $a_n$ and $b_n$ are $0$).
Take $x_0$ modulo $3$. It is apparent that we must have $x_0 = a_0 = b_0 mod 3$, which of course implies that $a_0 = b_0$. Now, consider $x_1:=frac{x_0 - a_0}{3}$. It is an integer, so it makes sense to reduce it modulo $3$ again---this time, we get the equality $x_1 = a_1 = b_1 mod 3$, so $a_1 = b_1$. Define $x_2 := frac{x_1 - a_1}{3}$, rinse, and repeat. An easy induction proves the result.
answered Jan 6 '15 at 1:46
Arseniy SheydvasserArseniy Sheydvasser
1263
$endgroup$
If you know a bit about modular arithmetic, then there is a relatively easy way to work this out (it is equivalent to the proofs already here, but perhaps is a little cleaner conceptually). Suppose that you have $x_0 = sum_{n = 0}^infty a_n 3^n = sum_{n = 0}^infty b_n 3^n$ (with the understanding that for large enough $n$, $a_n$ and $b_n$ are $0$).
Take $x_0$ modulo $3$. It is apparent that we must have $x_0 = a_0 = b_0 mod 3$, which of course implies that $a_0 = b_0$. Now, consider $x_1:=frac{x_0 - a_0}{3}$. It is an integer, so it makes sense to reduce it modulo $3$ again---this time, we get the equality $x_1 = a_1 = b_1 mod 3$, so $a_1 = b_1$. Define $x_2 := frac{x_1 - a_1}{3}$, rinse, and repeat. An easy induction proves the result.
answered Jan 6 '15 at 1:46
Arseniy SheydvasserArseniy Sheydvasser
1263
answered Jan 6 '15 at 1:46
Arseniy SheydvasserArseniy Sheydvasser
1263
answered Jan 6 '15 at 1:46
Arseniy SheydvasserArseniy Sheydvasser
1263
answered Jan 6 '15 at 1:46
Arseniy SheydvasserArseniy Sheydvasser
1263
1263
$begingroup$
Thanks for breaking it down a bit more! That should help me get it all finished up :)
$endgroup$
– graydad
Jan 6 '15 at 2:51
add a comment |
$begingroup$
Thanks for breaking it down a bit more! That should help me get it all finished up :)
$endgroup$
– graydad
Jan 6 '15 at 2:51
$begingroup$
Thanks for breaking it down a bit more! That should help me get it all finished up :)
$endgroup$
– graydad
Jan 6 '15 at 2:51
$begingroup$
Thanks for breaking it down a bit more! That should help me get it all finished up :)
$endgroup$
– graydad
Jan 6 '15 at 2:51
add a comment |
$begingroup$
The best approach is to use induction.
If $sum a_i3^i = sum b_i3^i$, first show that $a_0=b_0$ and thus that:$$sum_{i>0} a_i3^{i-1} = sum_{i>0} b_i3^{i-1}$$
Then apply the induction hypothesis.
answered Jan 5 '15 at 16:10
Thomas AndrewsThomas Andrews
130k12147298
$endgroup$
$begingroup$
Thank you, I will give this a shot. Why did you subtract $1$ from $i$ in the exponent after showing $a_0=b_0$?
$endgroup$
– graydad
Jan 5 '15 at 16:28
$begingroup$
The claim you are proving by induction considers sums which range from terms starting with $3^0$.
$endgroup$
– dalastboss
Jan 6 '15 at 2:14
add a comment |
$begingroup$
The best approach is to use induction.
If $sum a_i3^i = sum b_i3^i$, first show that $a_0=b_0$ and thus that:$$sum_{i>0} a_i3^{i-1} = sum_{i>0} b_i3^{i-1}$$
Then apply the induction hypothesis.
answered Jan 5 '15 at 16:10
Thomas AndrewsThomas Andrews
130k12147298
$endgroup$
$begingroup$
Thank you, I will give this a shot. Why did you subtract $1$ from $i$ in the exponent after showing $a_0=b_0$?
$endgroup$
– graydad
Jan 5 '15 at 16:28
$begingroup$
The claim you are proving by induction considers sums which range from terms starting with $3^0$.
$endgroup$
– dalastboss
Jan 6 '15 at 2:14
add a comment |
$begingroup$
The best approach is to use induction.
If $sum a_i3^i = sum b_i3^i$, first show that $a_0=b_0$ and thus that:$$sum_{i>0} a_i3^{i-1} = sum_{i>0} b_i3^{i-1}$$
Then apply the induction hypothesis.
answered Jan 5 '15 at 16:10
Thomas AndrewsThomas Andrews
130k12147298
$endgroup$
The best approach is to use induction.
If $sum a_i3^i = sum b_i3^i$, first show that $a_0=b_0$ and thus that:$$sum_{i>0} a_i3^{i-1} = sum_{i>0} b_i3^{i-1}$$
Then apply the induction hypothesis.
answered Jan 5 '15 at 16:10
Thomas AndrewsThomas Andrews
130k12147298
answered Jan 5 '15 at 16:10
Thomas AndrewsThomas Andrews
130k12147298
answered Jan 5 '15 at 16:10
Thomas AndrewsThomas Andrews
130k12147298
answered Jan 5 '15 at 16:10
Thomas AndrewsThomas Andrews
130k12147298
130k12147298
$begingroup$
Thank you, I will give this a shot. Why did you subtract $1$ from $i$ in the exponent after showing $a_0=b_0$?
$endgroup$
– graydad
Jan 5 '15 at 16:28
$begingroup$
The claim you are proving by induction considers sums which range from terms starting with $3^0$.
$endgroup$
– dalastboss
Jan 6 '15 at 2:14
add a comment |
$begingroup$
Thank you, I will give this a shot. Why did you subtract $1$ from $i$ in the exponent after showing $a_0=b_0$?
$endgroup$
– graydad
Jan 5 '15 at 16:28
$begingroup$
The claim you are proving by induction considers sums which range from terms starting with $3^0$.
$endgroup$
– dalastboss
Jan 6 '15 at 2:14
$begingroup$
Thank you, I will give this a shot. Why did you subtract $1$ from $i$ in the exponent after showing $a_0=b_0$?
$endgroup$
– graydad
Jan 5 '15 at 16:28
$begingroup$
Thank you, I will give this a shot. Why did you subtract $1$ from $i$ in the exponent after showing $a_0=b_0$?
$endgroup$
– graydad
Jan 5 '15 at 16:28
$begingroup$
The claim you are proving by induction considers sums which range from terms starting with $3^0$.
$endgroup$
– dalastboss
Jan 6 '15 at 2:14
$begingroup$
The claim you are proving by induction considers sums which range from terms starting with $3^0$.
$endgroup$
– dalastboss
Jan 6 '15 at 2:14
add a comment |
$begingroup$
Hint $ $ Viewing radix representation as a polynomial in the radix, this can be reduced to a result related to the rational root test - see the result below, which, slightly modified, also works here.
If $,g(x) = sum g_i x^i$ is a polynomial with integer coefficients $,g_i,$ such that $,0le g_i < b,$ and $,g(b) = n,$ then we call $,(g,b),$ the radix $,b,$ representation of $,n.,$ It is unique: $ $ if $,n,$ has another rep $,(h,b),,$ with $,g(x) ne h(x),,$ then $,f(x)= g(x)-h(x)ne 0,$ has root $,b,$ but all coefficients $,color{#c00}{|f_i| < b},,$ contra the following slight generalization of: $ $ integer roots of integer polynomials divide their constant term.
Theorem $ $ If $,f(x) = x^k(color{#0a0}{f_0}!+f_1 x +cdots + f_n x^n)=x^kbar f(x),$ is a polynomial with integer coefficients $,f_i,$ and with $,color{#0a0}{f_0ne 0},$ then an integer root $,bne 0,$ satisfies $,bmid f_0,,$ so $,color{#c00}{|b| le |f_0|}$
Proof $, 0 = f(b) = b^k bar f(b),overset{large b,ne, 0}Rightarrow, 0 = bar f(b),,$ so, subtracting $,f_0$ from both sides yields $$-f_0 =, b,(f_1!+f_2 b+,cdots+f_n b^{n-1}), Rightarrow,bmid f_0, overset{large color{#0a0}{f_0,ne, 0}}Rightarrow, |b| le |f_0|qquad {bf QED}qquadquad$$
answered Jan 5 '15 at 16:18
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
add a comment |
$begingroup$
Hint $ $ Viewing radix representation as a polynomial in the radix, this can be reduced to a result related to the rational root test - see the result below, which, slightly modified, also works here.
If $,g(x) = sum g_i x^i$ is a polynomial with integer coefficients $,g_i,$ such that $,0le g_i < b,$ and $,g(b) = n,$ then we call $,(g,b),$ the radix $,b,$ representation of $,n.,$ It is unique: $ $ if $,n,$ has another rep $,(h,b),,$ with $,g(x) ne h(x),,$ then $,f(x)= g(x)-h(x)ne 0,$ has root $,b,$ but all coefficients $,color{#c00}{|f_i| < b},,$ contra the following slight generalization of: $ $ integer roots of integer polynomials divide their constant term.
Theorem $ $ If $,f(x) = x^k(color{#0a0}{f_0}!+f_1 x +cdots + f_n x^n)=x^kbar f(x),$ is a polynomial with integer coefficients $,f_i,$ and with $,color{#0a0}{f_0ne 0},$ then an integer root $,bne 0,$ satisfies $,bmid f_0,,$ so $,color{#c00}{|b| le |f_0|}$
Proof $, 0 = f(b) = b^k bar f(b),overset{large b,ne, 0}Rightarrow, 0 = bar f(b),,$ so, subtracting $,f_0$ from both sides yields $$-f_0 =, b,(f_1!+f_2 b+,cdots+f_n b^{n-1}), Rightarrow,bmid f_0, overset{large color{#0a0}{f_0,ne, 0}}Rightarrow, |b| le |f_0|qquad {bf QED}qquadquad$$
answered Jan 5 '15 at 16:18
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
add a comment |
$begingroup$
Hint $ $ Viewing radix representation as a polynomial in the radix, this can be reduced to a result related to the rational root test - see the result below, which, slightly modified, also works here.
If $,g(x) = sum g_i x^i$ is a polynomial with integer coefficients $,g_i,$ such that $,0le g_i < b,$ and $,g(b) = n,$ then we call $,(g,b),$ the radix $,b,$ representation of $,n.,$ It is unique: $ $ if $,n,$ has another rep $,(h,b),,$ with $,g(x) ne h(x),,$ then $,f(x)= g(x)-h(x)ne 0,$ has root $,b,$ but all coefficients $,color{#c00}{|f_i| < b},,$ contra the following slight generalization of: $ $ integer roots of integer polynomials divide their constant term.
Theorem $ $ If $,f(x) = x^k(color{#0a0}{f_0}!+f_1 x +cdots + f_n x^n)=x^kbar f(x),$ is a polynomial with integer coefficients $,f_i,$ and with $,color{#0a0}{f_0ne 0},$ then an integer root $,bne 0,$ satisfies $,bmid f_0,,$ so $,color{#c00}{|b| le |f_0|}$
Proof $, 0 = f(b) = b^k bar f(b),overset{large b,ne, 0}Rightarrow, 0 = bar f(b),,$ so, subtracting $,f_0$ from both sides yields $$-f_0 =, b,(f_1!+f_2 b+,cdots+f_n b^{n-1}), Rightarrow,bmid f_0, overset{large color{#0a0}{f_0,ne, 0}}Rightarrow, |b| le |f_0|qquad {bf QED}qquadquad$$
answered Jan 5 '15 at 16:18
Bill DubuqueBill Dubuque
212k29195654
$endgroup$
Hint $ $ Viewing radix representation as a polynomial in the radix, this can be reduced to a result related to the rational root test - see the result below, which, slightly modified, also works here.
If $,g(x) = sum g_i x^i$ is a polynomial with integer coefficients $,g_i,$ such that $,0le g_i < b,$ and $,g(b) = n,$ then we call $,(g,b),$ the radix $,b,$ representation of $,n.,$ It is unique: $ $ if $,n,$ has another rep $,(h,b),,$ with $,g(x) ne h(x),,$ then $,f(x)= g(x)-h(x)ne 0,$ has root $,b,$ but all coefficients $,color{#c00}{|f_i| < b},,$ contra the following slight generalization of: $ $ integer roots of integer polynomials divide their constant term.
Theorem $ $ If $,f(x) = x^k(color{#0a0}{f_0}!+f_1 x +cdots + f_n x^n)=x^kbar f(x),$ is a polynomial with integer coefficients $,f_i,$ and with $,color{#0a0}{f_0ne 0},$ then an integer root $,bne 0,$ satisfies $,bmid f_0,,$ so $,color{#c00}{|b| le |f_0|}$
Proof $, 0 = f(b) = b^k bar f(b),overset{large b,ne, 0}Rightarrow, 0 = bar f(b),,$ so, subtracting $,f_0$ from both sides yields $$-f_0 =, b,(f_1!+f_2 b+,cdots+f_n b^{n-1}), Rightarrow,bmid f_0, overset{large color{#0a0}{f_0,ne, 0}}Rightarrow, |b| le |f_0|qquad {bf QED}qquadquad$$
answered Jan 5 '15 at 16:18
Bill DubuqueBill Dubuque
212k29195654
answered Jan 5 '15 at 16:18
Bill DubuqueBill Dubuque
212k29195654
answered Jan 5 '15 at 16:18
Bill DubuqueBill Dubuque
212k29195654
answered Jan 5 '15 at 16:18
Bill DubuqueBill Dubuque
212k29195654
212k29195654
add a comment |
add a comment |
$begingroup$
Hint:
- Note that $$(3^m+3^{m-1}+ldots+1)-(-3^m-3^{m-1}-ldots-1)=3^{m+1}-1$$ since $3-1=2$ and $3^{m+1}-1=3cdot3^m-1=2cdot3^m+(3^m-1)$.
- You could strengthen your argument so that each integer from $(-3^m-ldots-1)$ to $(3^m+ldots+1)$ can be expressed.
- In such case you are representing $3^{m+1}$ possibilities with at most $3^{m+1}$ different sums, that is, you get uniqueness for almost free.
- The first bullet makes for an elegant induction hypothesis, because $$3^{m+1}+(-3^m-3^{m-1}-ldots-1) = (3^m+3^{m-1}+ldots+1)+1.$$
I hope this helps $ddotsmile$
answered Jan 5 '15 at 16:40
dtldarekdtldarek
32.5k745101
$endgroup$
$begingroup$
@graydad That was a typo, updated now.
$endgroup$
– dtldarek
Jan 5 '15 at 16:47
$begingroup$
I'm still unsure how you get the first equality. Is it $$(3^{m+1}+3^{m}+ldots+3^1)-(-3^m-3^{m-1}-ldots-3^1-1)=3^{m+1}-1$$
$endgroup$
– graydad
Jan 5 '15 at 16:48
$begingroup$
@graydad After simplifying you get $2cdot 3^m+2cdot3^{m-1}+ldots+2 = 3^{m+1}-1$, which is intuitively true because it is the highest $m$-digit number you can get in the ordinary base-3, i.e. $22222ldots222_text{base 3}$.
$endgroup$
– dtldarek
Jan 5 '15 at 16:56
$begingroup$
Ah I see it now. Thank you for explaining further. I will play around with this result :)
$endgroup$
– graydad
Jan 5 '15 at 17:06
add a comment |
$begingroup$
Hint:
- Note that $$(3^m+3^{m-1}+ldots+1)-(-3^m-3^{m-1}-ldots-1)=3^{m+1}-1$$ since $3-1=2$ and $3^{m+1}-1=3cdot3^m-1=2cdot3^m+(3^m-1)$.
- You could strengthen your argument so that each integer from $(-3^m-ldots-1)$ to $(3^m+ldots+1)$ can be expressed.
- In such case you are representing $3^{m+1}$ possibilities with at most $3^{m+1}$ different sums, that is, you get uniqueness for almost free.
- The first bullet makes for an elegant induction hypothesis, because $$3^{m+1}+(-3^m-3^{m-1}-ldots-1) = (3^m+3^{m-1}+ldots+1)+1.$$
I hope this helps $ddotsmile$
answered Jan 5 '15 at 16:40
dtldarekdtldarek
32.5k745101
$endgroup$
$begingroup$
@graydad That was a typo, updated now.
$endgroup$
– dtldarek
Jan 5 '15 at 16:47
$begingroup$
I'm still unsure how you get the first equality. Is it $$(3^{m+1}+3^{m}+ldots+3^1)-(-3^m-3^{m-1}-ldots-3^1-1)=3^{m+1}-1$$
$endgroup$
– graydad
Jan 5 '15 at 16:48
$begingroup$
@graydad After simplifying you get $2cdot 3^m+2cdot3^{m-1}+ldots+2 = 3^{m+1}-1$, which is intuitively true because it is the highest $m$-digit number you can get in the ordinary base-3, i.e. $22222ldots222_text{base 3}$.
$endgroup$
– dtldarek
Jan 5 '15 at 16:56
$begingroup$
Ah I see it now. Thank you for explaining further. I will play around with this result :)
$endgroup$
– graydad
Jan 5 '15 at 17:06
add a comment |
$begingroup$
Hint:
- Note that $$(3^m+3^{m-1}+ldots+1)-(-3^m-3^{m-1}-ldots-1)=3^{m+1}-1$$ since $3-1=2$ and $3^{m+1}-1=3cdot3^m-1=2cdot3^m+(3^m-1)$.
- You could strengthen your argument so that each integer from $(-3^m-ldots-1)$ to $(3^m+ldots+1)$ can be expressed.
- In such case you are representing $3^{m+1}$ possibilities with at most $3^{m+1}$ different sums, that is, you get uniqueness for almost free.
- The first bullet makes for an elegant induction hypothesis, because $$3^{m+1}+(-3^m-3^{m-1}-ldots-1) = (3^m+3^{m-1}+ldots+1)+1.$$
I hope this helps $ddotsmile$
answered Jan 5 '15 at 16:40
dtldarekdtldarek
32.5k745101
$endgroup$
Hint:
- Note that $$(3^m+3^{m-1}+ldots+1)-(-3^m-3^{m-1}-ldots-1)=3^{m+1}-1$$ since $3-1=2$ and $3^{m+1}-1=3cdot3^m-1=2cdot3^m+(3^m-1)$.
- You could strengthen your argument so that each integer from $(-3^m-ldots-1)$ to $(3^m+ldots+1)$ can be expressed.
- In such case you are representing $3^{m+1}$ possibilities with at most $3^{m+1}$ different sums, that is, you get uniqueness for almost free.
- The first bullet makes for an elegant induction hypothesis, because $$3^{m+1}+(-3^m-3^{m-1}-ldots-1) = (3^m+3^{m-1}+ldots+1)+1.$$
I hope this helps $ddotsmile$
answered Jan 5 '15 at 16:40
dtldarekdtldarek
32.5k745101
edited Jan 5 '15 at 17:03
answered Jan 5 '15 at 16:40
dtldarekdtldarek
32.5k745101
answered Jan 5 '15 at 16:40
dtldarekdtldarek
32.5k745101
answered Jan 5 '15 at 16:40
dtldarekdtldarek
32.5k745101
32.5k745101
$begingroup$
@graydad That was a typo, updated now.
$endgroup$
– dtldarek
Jan 5 '15 at 16:47
$begingroup$
I'm still unsure how you get the first equality. Is it $$(3^{m+1}+3^{m}+ldots+3^1)-(-3^m-3^{m-1}-ldots-3^1-1)=3^{m+1}-1$$
$endgroup$
– graydad
Jan 5 '15 at 16:48
$begingroup$
@graydad After simplifying you get $2cdot 3^m+2cdot3^{m-1}+ldots+2 = 3^{m+1}-1$, which is intuitively true because it is the highest $m$-digit number you can get in the ordinary base-3, i.e. $22222ldots222_text{base 3}$.
$endgroup$
– dtldarek
Jan 5 '15 at 16:56
$begingroup$
Ah I see it now. Thank you for explaining further. I will play around with this result :)
$endgroup$
– graydad
Jan 5 '15 at 17:06
add a comment |
$begingroup$
@graydad That was a typo, updated now.
$endgroup$
– dtldarek
Jan 5 '15 at 16:47
$begingroup$
I'm still unsure how you get the first equality. Is it $$(3^{m+1}+3^{m}+ldots+3^1)-(-3^m-3^{m-1}-ldots-3^1-1)=3^{m+1}-1$$
$endgroup$
– graydad
Jan 5 '15 at 16:48
$begingroup$
@graydad After simplifying you get $2cdot 3^m+2cdot3^{m-1}+ldots+2 = 3^{m+1}-1$, which is intuitively true because it is the highest $m$-digit number you can get in the ordinary base-3, i.e. $22222ldots222_text{base 3}$.
$endgroup$
– dtldarek
Jan 5 '15 at 16:56
$begingroup$
Ah I see it now. Thank you for explaining further. I will play around with this result :)
$endgroup$
– graydad
Jan 5 '15 at 17:06
$begingroup$
@graydad That was a typo, updated now.
$endgroup$
– dtldarek
Jan 5 '15 at 16:47
$begingroup$
@graydad That was a typo, updated now.
$endgroup$
– dtldarek
Jan 5 '15 at 16:47
$begingroup$
I'm still unsure how you get the first equality. Is it $$(3^{m+1}+3^{m}+ldots+3^1)-(-3^m-3^{m-1}-ldots-3^1-1)=3^{m+1}-1$$
$endgroup$
– graydad
Jan 5 '15 at 16:48
$begingroup$
I'm still unsure how you get the first equality. Is it $$(3^{m+1}+3^{m}+ldots+3^1)-(-3^m-3^{m-1}-ldots-3^1-1)=3^{m+1}-1$$
$endgroup$
– graydad
Jan 5 '15 at 16:48
$begingroup$
@graydad After simplifying you get $2cdot 3^m+2cdot3^{m-1}+ldots+2 = 3^{m+1}-1$, which is intuitively true because it is the highest $m$-digit number you can get in the ordinary base-3, i.e. $22222ldots222_text{base 3}$.
$endgroup$
– dtldarek
Jan 5 '15 at 16:56
$begingroup$
@graydad After simplifying you get $2cdot 3^m+2cdot3^{m-1}+ldots+2 = 3^{m+1}-1$, which is intuitively true because it is the highest $m$-digit number you can get in the ordinary base-3, i.e. $22222ldots222_text{base 3}$.
$endgroup$
– dtldarek
Jan 5 '15 at 16:56
$begingroup$
Ah I see it now. Thank you for explaining further. I will play around with this result :)
$endgroup$
– graydad
Jan 5 '15 at 17:06
$begingroup$
Ah I see it now. Thank you for explaining further. I will play around with this result :)
$endgroup$
– graydad
Jan 5 '15 at 17:06
add a comment |
$begingroup$
Outline of Proof:
1) first assume n has a representation as required
2) Show that for each representation of $n$ we can find a representation for $n-1$. This means if we know a representation for an integer greater than $n$, we can find one for $n$.
3)$3^n$ is greater than n and has a representation; therefore so does $n$
4)Squeeze the number of representations for $n$ between 1 and 1.
Suppose that n has a representation of the form $n = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0$. Now we want to subtract 1 from both sides, $n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0-1$. Now, $n-1$ does not have the proper representation yet. On its own $-1$ can be written $-1=-1*3^0$. We can now write $n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0$.
We want to say here that given a representation of $n$ satisfying the requirements we can find a representation of $n-1$ that does as well, but for the case $c_0=-1$ we get a coefficient of $-2$ for the last term.
So for the case $c_0=-1$ we will use the formula $-2*3^j=-3^{j+1}+3^j$ to rewrite $n-1$.$n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0=c_m3^m+c_{m-1}3^{m-1}+...-2*3^0=c_m3^m+c_{m-1}3^{m-1}+...-3^1+3^0$. Now we realize that there may exist a term w/ coefficient $-1$ and exponent $1$ and we are back where we started.
But, there must exist a last term with $-1$ as a coefficient. Let the kth term be the last one with coefficient $-1$, then we have $n-1=c_m3^m+c_{m-1}3^{m-1}+...-3^{k+1}+3^k+3^{k-1}+...+3^0
$ and this representation meets the requirements.
So we have shown that for each representation of $n$ we can find a representation for $n-1
$. Since $3^n>n>0$ and $3^n$ has a representation(itself) then a representation for n can be found progressively.
Uniqueness:
Let $b_k(n)$ represent the total number of representations for $n$. Since for each representation of $n$ we can find one for $n-1$ we have $b_k(n)$<=$b_k(n-1)$. (Skipping a bit) we have finally 1<=$b_k(3^n)<=b_k(n)<=b_k(1)=1$.
The total number of representations for $n$ is between $1$ and $1$ and must therefore be $1$
answered Jan 23 '15 at 3:31
Vladimir LouisVladimir Louis
1027
$endgroup$
add a comment |
$begingroup$
Outline of Proof:
1) first assume n has a representation as required
2) Show that for each representation of $n$ we can find a representation for $n-1$. This means if we know a representation for an integer greater than $n$, we can find one for $n$.
3)$3^n$ is greater than n and has a representation; therefore so does $n$
4)Squeeze the number of representations for $n$ between 1 and 1.
Suppose that n has a representation of the form $n = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0$. Now we want to subtract 1 from both sides, $n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0-1$. Now, $n-1$ does not have the proper representation yet. On its own $-1$ can be written $-1=-1*3^0$. We can now write $n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0$.
We want to say here that given a representation of $n$ satisfying the requirements we can find a representation of $n-1$ that does as well, but for the case $c_0=-1$ we get a coefficient of $-2$ for the last term.
So for the case $c_0=-1$ we will use the formula $-2*3^j=-3^{j+1}+3^j$ to rewrite $n-1$.$n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0=c_m3^m+c_{m-1}3^{m-1}+...-2*3^0=c_m3^m+c_{m-1}3^{m-1}+...-3^1+3^0$. Now we realize that there may exist a term w/ coefficient $-1$ and exponent $1$ and we are back where we started.
But, there must exist a last term with $-1$ as a coefficient. Let the kth term be the last one with coefficient $-1$, then we have $n-1=c_m3^m+c_{m-1}3^{m-1}+...-3^{k+1}+3^k+3^{k-1}+...+3^0
$ and this representation meets the requirements.
So we have shown that for each representation of $n$ we can find a representation for $n-1
$. Since $3^n>n>0$ and $3^n$ has a representation(itself) then a representation for n can be found progressively.
Uniqueness:
Let $b_k(n)$ represent the total number of representations for $n$. Since for each representation of $n$ we can find one for $n-1$ we have $b_k(n)$<=$b_k(n-1)$. (Skipping a bit) we have finally 1<=$b_k(3^n)<=b_k(n)<=b_k(1)=1$.
The total number of representations for $n$ is between $1$ and $1$ and must therefore be $1$
answered Jan 23 '15 at 3:31
Vladimir LouisVladimir Louis
1027
$endgroup$
add a comment |
$begingroup$
Outline of Proof:
1) first assume n has a representation as required
2) Show that for each representation of $n$ we can find a representation for $n-1$. This means if we know a representation for an integer greater than $n$, we can find one for $n$.
3)$3^n$ is greater than n and has a representation; therefore so does $n$
4)Squeeze the number of representations for $n$ between 1 and 1.
Suppose that n has a representation of the form $n = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0$. Now we want to subtract 1 from both sides, $n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0-1$. Now, $n-1$ does not have the proper representation yet. On its own $-1$ can be written $-1=-1*3^0$. We can now write $n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0$.
We want to say here that given a representation of $n$ satisfying the requirements we can find a representation of $n-1$ that does as well, but for the case $c_0=-1$ we get a coefficient of $-2$ for the last term.
So for the case $c_0=-1$ we will use the formula $-2*3^j=-3^{j+1}+3^j$ to rewrite $n-1$.$n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0=c_m3^m+c_{m-1}3^{m-1}+...-2*3^0=c_m3^m+c_{m-1}3^{m-1}+...-3^1+3^0$. Now we realize that there may exist a term w/ coefficient $-1$ and exponent $1$ and we are back where we started.
But, there must exist a last term with $-1$ as a coefficient. Let the kth term be the last one with coefficient $-1$, then we have $n-1=c_m3^m+c_{m-1}3^{m-1}+...-3^{k+1}+3^k+3^{k-1}+...+3^0
$ and this representation meets the requirements.
So we have shown that for each representation of $n$ we can find a representation for $n-1
$. Since $3^n>n>0$ and $3^n$ has a representation(itself) then a representation for n can be found progressively.
Uniqueness:
Let $b_k(n)$ represent the total number of representations for $n$. Since for each representation of $n$ we can find one for $n-1$ we have $b_k(n)$<=$b_k(n-1)$. (Skipping a bit) we have finally 1<=$b_k(3^n)<=b_k(n)<=b_k(1)=1$.
The total number of representations for $n$ is between $1$ and $1$ and must therefore be $1$
answered Jan 23 '15 at 3:31
Vladimir LouisVladimir Louis
1027
$endgroup$
Outline of Proof:
1) first assume n has a representation as required
2) Show that for each representation of $n$ we can find a representation for $n-1$. This means if we know a representation for an integer greater than $n$, we can find one for $n$.
3)$3^n$ is greater than n and has a representation; therefore so does $n$
4)Squeeze the number of representations for $n$ between 1 and 1.
Suppose that n has a representation of the form $n = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0$. Now we want to subtract 1 from both sides, $n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+c_03^0-1$. Now, $n-1$ does not have the proper representation yet. On its own $-1$ can be written $-1=-1*3^0$. We can now write $n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0$.
We want to say here that given a representation of $n$ satisfying the requirements we can find a representation of $n-1$ that does as well, but for the case $c_0=-1$ we get a coefficient of $-2$ for the last term.
So for the case $c_0=-1$ we will use the formula $-2*3^j=-3^{j+1}+3^j$ to rewrite $n-1$.$n-1 = sum_{i=0}^mc_i3^i=c_m3^m+c_{m-1}3^{m-1}+...+(c_0-1)3^0=c_m3^m+c_{m-1}3^{m-1}+...-2*3^0=c_m3^m+c_{m-1}3^{m-1}+...-3^1+3^0$. Now we realize that there may exist a term w/ coefficient $-1$ and exponent $1$ and we are back where we started.
But, there must exist a last term with $-1$ as a coefficient. Let the kth term be the last one with coefficient $-1$, then we have $n-1=c_m3^m+c_{m-1}3^{m-1}+...-3^{k+1}+3^k+3^{k-1}+...+3^0
$ and this representation meets the requirements.
So we have shown that for each representation of $n$ we can find a representation for $n-1
$. Since $3^n>n>0$ and $3^n$ has a representation(itself) then a representation for n can be found progressively.
Uniqueness:
Let $b_k(n)$ represent the total number of representations for $n$. Since for each representation of $n$ we can find one for $n-1$ we have $b_k(n)$<=$b_k(n-1)$. (Skipping a bit) we have finally 1<=$b_k(3^n)<=b_k(n)<=b_k(1)=1$.
The total number of representations for $n$ is between $1$ and $1$ and must therefore be $1$
answered Jan 23 '15 at 3:31
Vladimir LouisVladimir Louis
1027
edited Sep 14 '17 at 18:56
answered Jan 23 '15 at 3:31
Vladimir LouisVladimir Louis
1027
answered Jan 23 '15 at 3:31
Vladimir LouisVladimir Louis
1027
answered Jan 23 '15 at 3:31
Vladimir LouisVladimir Louis
1027
1027
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1091962%2funiqueness-of-radix-representation-of-integers-in-base-3%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Suppose $b_{m+1} = 1$. Then even if all the $c_i - b_i = 1$, maximizing the expression on the right, then that sum would still be less than $3^{m+1}$. There is a similar case for $b_{m+1} = -1$. For the case $b_{m+1} = 0$, there must be some $b_j neq 0$, $j > m+1$.
$endgroup$
– Simon S
Jan 5 '15 at 16:09
1
$begingroup$
Note that that's called "balanced ternary," whereas just "ternary" usually means base $3$ with the digits $0$, $1$, $2$. Thus, in ternary, $26$ is $222$ but in balanced ternary you'd have a $1$ followed by two $0$s and ending with a $-1$.
$endgroup$
– user153918
Jan 5 '15 at 18:26