anonymous
  • anonymous
Can anyone explain George E. Andrews proof of Basis Representation Theorem?
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
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.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
this is what you're talking about? http://puu.sh/iMtN8/0b7006bf62.png
anonymous
  • anonymous
i am sure it is in a textbook that is why they cost like $250
anonymous
  • anonymous
I have the book. I'm having difficulty following the proof

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
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
anonymous
  • anonymous
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\)
anonymous
  • anonymous
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\)
anonymous
  • anonymous
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?
anonymous
  • anonymous
and why is it written differently from the way it was written in theorem?
anonymous
  • anonymous
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}\))
anonymous
  • anonymous
i'm still not getting it :/
anonymous
  • anonymous
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
anonymous
  • anonymous
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)\)
anonymous
  • anonymous
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\)
anonymous
  • anonymous
actually, oops, earlier I meant the first \(t\) digits of the \(s\)-digit-long expansion of \(n\) in base \(k\) are \(0\)
anonymous
  • anonymous
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?
anonymous
  • anonymous
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\))
ganeshie8
  • ganeshie8
this uniqueness part looks unnecessarily complicated
anonymous
  • anonymous
and recall that if \(f:A\to B\) is an injection then \(|A|\le |B|\)
anonymous
  • anonymous
pigeonhole principle
anonymous
  • anonymous
@ganeshie8 the beauty is that it does existence and uniqueness simultaneously to show that \(b_k(n)=1\) in one swoop !
anonymous
  • anonymous
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?
anonymous
  • anonymous
yes! so therefore there must be at least one representation of \(n-2\) for every representation of \(n-1\), and possibly more
ganeshie8
  • ganeshie8
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..
anonymous
  • anonymous
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?
anonymous
  • anonymous
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\))
anonymous
  • anonymous
and yes @sourwing, we have that \(b_k\) is decreasing on the natural numbers
anonymous
  • anonymous
ok, here is the stupid question. Why is b_k(1) = 1? XD and also b_k(k^n) = 1
anonymous
  • anonymous
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\)
anonymous
  • anonymous
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\)
anonymous
  • anonymous
but that's enough for us since we're only using \(b^k(k^p)\) as a lower-bound
anonymous
  • anonymous
ah yeah because 1 <= b_k(k^n) <=1 thus b_k(k^n) = 1
anonymous
  • anonymous
oops, \(b_k(k^n)\) as a lower bound* and yes exactly, it gets sandwiched between
anonymous
  • anonymous
Much thanks @oldrin.bataku :') I have a better understanding of the proof now. Thanks. @ganeshie8 thank you for giving replies too :)
Empty
  • Empty
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.
anonymous
  • anonymous
that's not really relevant here; he's interested in vanilla base-\(k\) representations of positive integers
Empty
  • Empty
Yeah I know
anonymous
  • anonymous
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$$
anonymous
  • anonymous
by 'works' i mean gives unique representations
Empty
  • Empty
Sure this is just one instance, we don't have to have the basis following any pattern at all.
ganeshie8
  • ganeshie8
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
anonymous
  • anonymous
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
anonymous
  • anonymous
i think there are some conditions you need to prove as well to ensure that's enough @ganeshie8
ganeshie8
  • ganeshie8
like \(a_0,~~a'_0\ne 0\) and \(a_{s-t},~~a'_{s-t}\ne 0\) ?
anonymous
  • anonymous
nah, but I think it's trivial anyways
anonymous
  • anonymous
@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

Looking for something else?

Not the answer you are looking for? Search for more explanations.