For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Hi,

with this topic, continues the saga "how this guy can ask that? it's obvious!"
I have this theorem and post here a part of the proof:
Let g be greater than 1. Then each integer a greater than 0 can be represented uniquely in the form
a = c_0 + c_1g + ... + c_ng^n

where c_n is positive and 0 \le c_m < g for 0 \le m \le n.
Proof: We prove the representability by induction on a.
For a = 1, we have n = 0 and c_0 = 1.
Take a greater than 1 and assume that the theorem is true for 1, 2, ... , a - 1. Since g is larger than 1, the numbers g^0, g^1, g^2, ... form an increasing sequence, and any positive integer lies between some pair of successive
powers of g. More explicitly, there is a unique n > 0 such that gn \le a < g^{n + 1}.
By Theorem:
If a is positive and b is arbitrary, there is exactly one pair of integers q, r such that the conditions
b = qa + r, 0 \le r < a,
hold.

there are unique integers c_n and r such that
a = c_ng^n + r, 0 \le r < g^n.

Here c_n > 0, since c_ng^n = a - r > g^n - g^n = 0; moreover, c_n < g because c_ng^n \le a < g^{n+1}.
...

I don't understand something in the last phrase.
From a = c_ng^n + r, I obtain
c_ng^n = a - r \Rightarrow c_ng^n = c_ng^n +r- r \Rightarrow 0 = 0
so how can I obtain c_n > 0?

And also c_n < g, I think that it has been obtained from g^nn \le a < g^{n + 1} as written above in the proof, but I don't understand why consider c_ng^n \le a < g^{n+1}

many thanks.

jacksmack

Posts: 54
Joined: Wed Mar 21, 2012 2:18 am UTC
Location: Italy

### Re: Radix representation by induction.

jacksmack wrote:so how can I obtain c_n > 0?
You have to read his explanation.

We already know that a >= gn. (This is how we chose n in the first place.) We also know that r < gn. Therefore, a - r > 0. But a-r is also equal to cngn, so cngn > 0, and that means gn > 0.

Does that make sense?
jacksmack wrote:I don't understand why consider c_ng^n \le a < g^{n+1}
Well, because that's how you prove it. We know cngn <= a, because of how we defined cn. And we know a < gn+1. Therefore, cngn < gn+1, and dividing both sides by gn we have cn < g.

If you have an alternative proof, maybe it is correct also, but I encourage you to write it down in detail so that we can find out.
++\$_
Mo' Money

Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

### Re: Radix representation by induction.

ok it's clear now!
Now I continue to post the proof:
If r = 0, then
a = 0 + 0 \cdot g + ... + 0 \cdot g^{n-1} + c_ng^n

whereas if r is positive, the induction hypothesis shows that r has a representation of the form
r = b_0 + b_1g + ... + b_tg^t,

where b_t is positive and 0 \le b_m < g for 0 \le m \le t. Moreover, t < n.
Thus
a=b_0 + b_1g + ... + b_tg^t + 0 \cdot g^{t+1} + ... + 0 \cdot g^{n-1} + c_ng^n,

where the terms with coefficient zero occur only if t + 1 < n. Now use the induction principle.
...

So it's clear that if r=0 when I replace r with zero in a=c_ng^n+r, I obtain a = 0 + 0 \cdot g + ... + 0 \cdot g^{n-1} + c_ng^n.

But it's not clear the case r positive.
how can the induction hypothesis shows that type of representation? What relation I have to see?

in the meantime I continue to post the proof:
(note: there is a bug in jsMath because, \ne for "is not equal" it is not rendered correcly, so I have replaced it with !=)
To prove uniqueness, assume that there are two distinct representations for a:
a=c_0+c_1g+...+c_ng^n=d_0+d_1g+...+d_rg^r

with n > 0, c_n > 0, and 0 \le c_m < g for 0 \le m \le n, and also r \ge 0, d_r > 0, and 0 \le d_m < g for 0 \le m \le r. Then by subtracting one of these representations of a from the other, we obtain an equation of the form
0 = e_0 + e_1g +...+e_sg^s,

where s is the largest value of m for which c_m != d_m, so that e_s != 0.
If s = 0, we have the contradiction e_0 = e = 0. If s > 0 we have
\left | e_m \right | = \left | c_m - d_m \right | \le g-1, \,\, 0\le m \le s-1

and
e_sg^s=-\left ( e_0+...+e_{s-1}g^{s-1} \right ),

so that
g^s \le \left | e_sg^s \right | = \left | e_0 + ... + e_{s-1}g^{s-1} \right | \le \left | e_0 \right | + ... + \left |e_{s-1} \right |g^{s-1}

\le \left (g-1 \right )\left (1+g+...+g^{s-1}\right ) = g^s - 1

which is also a contradiction. We conclude that n = r and c_m = d_m for 0 \le m \le n, and the representation is unique.

here I don't understand why \left | c_m - d_m \right | \le g-1

thanks.

jacksmack

Posts: 54
Joined: Wed Mar 21, 2012 2:18 am UTC
Location: Italy

### Re: Radix representation by induction.

0<=cm<=g-1 and 0<=dm<=g-1 are given by the definition of them. Use the upper bound of one and the lower bound of the other to get an upper bound of the difference.
mfb

Posts: 803
Joined: Thu Jan 08, 2009 7:48 pm UTC

### Re: Radix representation by induction.

No, I don't understand.

You are sayin' that I have to consider these 0 \le c_m < g, \ 0 \le d_m < g from definition, so c_m \ge 0, \, c_m<g and d_m \ge 0, \, d_m<g.
Hence the lower bound of c_m and the upper bound of d_m:
0 \le c_m, \, d_m<g

or the upper bound of c_m and the lower bound of d_m:
c_m <g, \, 0 \le d_m

But sorry still I don't understand how to obtain from that \left | c_m - d_m \right | \le g - 1.

jacksmack

Posts: 54
Joined: Wed Mar 21, 2012 2:18 am UTC
Location: Italy

### Re: Radix representation by induction.

If m and n are integers, then m < n means m+1 <= n, or m <= n-1.

So 0 <= cm < g means 0 <= cm <= g-1. Same bounds for dm.

Then

cm - dm >= 0 - (g-1) = -(g-1)
(-dm >= -(g-1) is equivalent to dm <= g-1.)

and

cm - dm <= (g-1) - 0 = (g-1);

these inequalities together imply that abs(cm-dm) <= g-1.

Proginoskes

Posts: 309
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down