Radix representation by induction.

[jacksmack]

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.

[++$_]

so how can I obtain c_n > 0?

You have to read his explanation.

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

Does that make sense?

I don't understand why consider c_ng^n \le a < g^{n+1}

Well, because that's how you prove it. We know c_ngⁿ <= a, because of how we defined c_n. And we know a < gⁿ⁺¹. Therefore, c_ngⁿ < gⁿ⁺¹, and dividing both sides by gⁿ we have c_n < 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.

[jacksmack]

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.

[mfb]

0<=c_m<=g-1 and 0<=d_m<=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.

[jacksmack]

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.

[Proginoskes]

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

So 0 <= c_m < g means 0 <= c_m <= g-1. Same bounds for d_m.

Then

c_m - d_m >= 0 - (g-1) = -(g-1)
(-d_m >= -(g-1) is equivalent to d_m <= g-1.)

and

c_m - d_m <= (g-1) - 0 = (g-1);

these inequalities together imply that abs(c_m-d_m) <= g-1.