Proof of Basis Rep Theorem: Let n=a_0k^s+...+a_tk^t

[Miike012]

Hello,


1. Proof: Let denote the number of representations of to the base . We must show that always equals 1.

(this means that we are trying to prove that there is only one representation?)

Line 2. Suppose that
$$n = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t}$$

then...

Line 3. $$n - 1 = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t} - 1 = a_{0}k^{s} + a_{1}k^{s-1} + ... + \left(a_{s-t} - 1\right)k^{t} + k^{t} - 1 = a_{0}k^{s} + a_{1}k^{s-1} + ... + \left(a_{s-t} - 1\right)k^{t} + \sum_{j=0}^{t-1} \left(k - 1\right)k^{t}$$


(I am not understanding the proof. How did line 2 get to line 3 algebraically?)

I am only in algebra right now... when will I learn how to read a proof and understand it?
Is there anything on the internet that someone can recommend reading so I will have a better understanding ?

Thanky you.

 

[ojs]

Line 3 is in many steps, do you not understand how it goes from line 2 into the first part of line 3? That is you don't understand why $$n = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t}$$ turns into $$n - 1 = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t} - 1$$? Or is it the rest of the 3'rd line that is confusing you?

 

[Miike012]

Yes... how do they go from
$$n = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t}$$

to

$$n - 1 = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t} - 1$$

It looks like they subtracted a one from each side... why?

 

[ojs]

Thats exactly what is done, subtract one from each side. As to why that is done then we have to look at the whole proof, a bit difficult to explain this over a forum like this. Try reading this text: http://www.proofwiki.org/wiki/Basis_Representation_Theorem and see if that is any clearer.

 

[Miike012]

Thank you...
The book that I am reading from is called number theory by george e. andrews... I don't like how the book gives a theorem then doesn't explain where it came from, for instance why the 1 was subtracted... are there any other books that are more detailed and explain step for step?

 

[ojs]

No, don't think there are any books out there that are more step to step than that.

But to try to explain it shortly then what is being done is that the proof is showing that for any positive whole number there is one and only one representation for it. To do that we give ourselves a representation for any positive whole number n, we subtract one from each side to see that we can get a representation for the number one below n as well.
Then we get that the number of representations for n is less then or equal to the number of representations of n-1 and from that he gets a bunch of inequalities that are used to show that the number of representations of n get squeezed between 1 and 1 and must therefore be 1, that is there is one and only 1 representation for n.

 

[ramsey2879]

Yes... how do they go from
$$n = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t}$$

to

$$n - 1 = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t} - 1$$

It looks like they subtracted a one from each side... why?

Many proofs are like that. Very often a 1st step to making a proof comes by determining a process of reducing it to such simple steps as that which can be repeated over and over to get to the "obvious" conclusion that the theorem is correct. If 1 is subtracted over and over then of course we will ultimately get to n - (n-1) or 1 and thus will have shown that each number from 1 to n has a representation. Also by comparing together each representation determined by this method will show that the representation for each number from 1 to n is unique. And since no limit was given to the value of n the therom holds for all integers. It is not for you to ask why this step until you have looked at the whole proof. As long as you determine each step is mathematically valid the question of whether the proof will work should be left undecided. Remember you are not the expert, you are the learner and should not be expected to know why an expert does certain things until after seeing the whole thing through to its conclusion. Only in due time will you begin to see immediately where each step has an obvious purpose before reaching the end of the proof. Until then certain steps simply can not be explained satisfactly except by stating that they are a means to the end result. That has already been stated by the naming of the work as a "proof". Only later the writer of the proof may see fit to explain how the steps do amount to a proof but until then it would be redundant to explain the purpose behind each step as one goes along.