Can anyone explain George E. Andrews proof of Basis Representation Theorem?

At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions.

A community for students.

Can anyone explain George E. Andrews proof of Basis Representation Theorem?

Mathematics
See more answers at brainly.com
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions

this is what you're talking about? http://puu.sh/iMtN8/0b7006bf62.png
i am sure it is in a textbook that is why they cost like $250
I have the book. I'm having difficulty following the proof

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

Here is the proof: https://books.google.com/books?id=NV68AQAAQBAJ&pg=PA8&lpg=PA8&dq=basis+representation+theorem+George+E+andrews&source=bl&ots=YCwCkKwHps&sig=L_OQ1YWGLClSs3pNQWEmCuWo4mU&hl=en&sa=X&ei=dzGXVc6DO4WtogSGqISgCw&ved=0CDsQ6AEwBA#v=onepage&q=basis%20representation%20theorem%20George%20E%20andrews&f=false
Well, it's done in a relatively unorthodox way. The idea is to tackle existence and uniqueness of a representation at the same time by defining \(b_k(n)\) to denote the # of representations of \(n\) in base \(k\) and then arguing \(b_k(n)=1\) for all integers \(n>0,k>1\)
the next tricky thing they do is use the fact that $$\sum_{j=0}^{t-1} k^j=\frac{k^t-1}{k-1}$$ to rewrite \(k^t-1=\sum\limits_{j=0}^{t-1}(k-1)k^j\)
yeah I understand the general idea. Ok, let's just go through line by line (well not completely). I already posted the link so here it goes: He said let b_k(n) be the number of representation for n. And we need to show that b_k(n) = 1. Ok Then he say some of the coefficient can be zero, thus, can be omitted. But then n = a_0 k^s + a_1 k^(s-1) + ... + a_(s-t) k^t <--- where does this come from?
and why is it written differently from the way it was written in theorem?
suppose we can represent \(n\) as a \(t\)-digit expansion in base \(k\); they're saying if the first \(s\) of the \(t\) digits of our representation then we're only looking at the \(s-t\) digits that matter in our sum (hence we why we don't write \(k^0,k^1,k^2,\dots,k^{s-1}\))
i'm still not getting it :/
oops, if the first \(s\) digits of our \(t\)-digit representation of \(n\) in base \(k\) are all zeros then we can forget them; to be honest this part isn't necessary
the important part is just to show that if we have a representation of \(n\), then we can derive a distinct representation of \(n-1\), so there are at least as many representations of \(n-1\) as there are of \(n\) -- in other words, \(b_k(n)\le b_k(n-1)\)
now we know that powers of \(k\) have only one representation trivially so we can use that inequality to bound \(b_k(n)\) between \(k^0=1\) and \(k^n\) which is guaranteed bigger than \(n\) since \(k>1\). we find: $$k^n>n>1\implies b_k(k^n)\le b_k(n)\le b_k(1)\implies b_k(n)=1$$ since \(b_k(k^n)=b_k(1)=1\)
actually, oops, earlier I meant the first \(t\) digits of the \(s\)-digit-long expansion of \(n\) in base \(k\) are \(0\)
Yeah, I understand the last part of the proof. It's the part where it says b_k (n) <= b_k(n-1) that gives me trouble. Why is this inequality true?
because we showed that every representation of \(n\) gives rise to its own representation of \(n-1\), thus it must be that there are at least as many representations of \(n-1\) as there are of \(n\) (basically there's an injection from the set of the representations of \(n\) to the set of representations of \(n-1\))
this uniqueness part looks unnecessarily complicated
and recall that if \(f:A\to B\) is an injection then \(|A|\le |B|\)
pigeonhole principle
@ganeshie8 the beauty is that it does existence and uniqueness simultaneously to show that \(b_k(n)=1\) in one swoop !
o: oh ok. so by the same argument if there is another representation for n-1, we use the same algebra and generate a representation for n-2?
yes! so therefore there must be at least one representation of \(n-2\) for every representation of \(n-1\), and possibly more
Oh yeah, I'm coming from euclid division algorithm and divisibility argument thats somewhat easier to follow for me... honestly i still don't get the George E. Andrews's proof, still going thru..
So the conclusion is that a smaller natural less than or equal to the number of representation of a bigger natural number? Isn't that what the statement b_k(m) <= b_k(m-1) <= ... <= b_(n-1) <= b_k(n) is saying?
it's honestly a quite beautiful trick; the part about $$k^t-1=\sum_{j=0}^{j-1}(k-1)k^j$$ is implicitly saying you 'borrow' from the last non-zero digit and then the others become 'nines' (or \(k-1\) in base \(k\))
and yes @sourwing, we have that \(b_k\) is decreasing on the natural numbers
ok, here is the stupid question. Why is b_k(1) = 1? XD and also b_k(k^n) = 1
because \(1=1_k\) is the same in every base \(k\) (since \(k^0=1\)) and any other digits would trivially result in something too big to be \(1\)
though to be fair they don't actually argue that \(b_k(k^p)=1\), they just argue that \(b_k(k^p)\ge 1\) since it permits at least one obvious representation -- the digit \(1\) followed by \(p\) zeros :) just like \(10^3=1000\)
but that's enough for us since we're only using \(b^k(k^p)\) as a lower-bound
ah yeah because 1 <= b_k(k^n) <=1 thus b_k(k^n) = 1
oops, \(b_k(k^n)\) as a lower bound* and yes exactly, it gets sandwiched between
Much thanks @oldrin.bataku :') I have a better understanding of the proof now. Thanks. @ganeshie8 thank you for giving replies too :)
You can don't even need to use powers of a number, you just need to multiply by any number greater than 2 to get he next place and one less than that is what you can hold. For instance a "factorial base" gives us a nice result such as: \[4! - 1 = 3*3!+2*2!+1*1!\] Which corresponds to a unique representation in the factorial base: \[1000_f - 1_f = 321_f\] Something fun to play with.
that's not really relevant here; he's interested in vanilla base-\(k\) representations of positive integers
Yeah I know
but I will say the reason that the factorial number system works is that the next 'place'-value \(P(n)\) satisfies a recurrence $$\sum_{n=0}^n (n-1)\cdot P(n)=P(n+1)-1$$
by 'works' i mean gives unique representations
Sure this is just one instance, we don't have to have the basis following any pattern at all.
just so you know why i felt it was complicated earlier... below argument looks simple enough for me let the two representations be \[n=a_0k^s+a_1k^{s-1}+\cdots+a_{s-t}k^t ~~=~~ a'_0k^s+a'_1k^{s-1}+\cdots+a'_{s-t}k^t \] subtract them and get \[0=(a_0-a'_0)k^s+(a_1-a'_1)k^{s-1}+\cdots+(a_{s-t}-a'{s-t})k^t\] divide \(k^t\) through out and argue that \(k\mid (a_{s-t}-a'_{s-t})\) is impossible
oops, i messed up that recurrence, but hopefully you know what i'm talking about; it's an elementary result in mixed-radix positional number systems
i think there are some conditions you need to prove as well to ensure that's enough @ganeshie8
like \(a_0,~~a'_0\ne 0\) and \(a_{s-t},~~a'_{s-t}\ne 0\) ?
nah, but I think it's trivial anyways
@ganeshie8 I hope Euclid Division proof is easier as you said earlier. I'm generally scared to read proofs on my own XD. But that's ok. Shooting dead ducks through airplane's engine seems like a fun way to test an newly manufactured plane. (nah i'm just being random right now XD) Thanks everyone! bye

Not the answer you are looking for?

Search for more explanations.

Ask your own question