1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof: Basis Representation Theorem

  1. Dec 30, 2008 #1
    I had a question about the following theorem.

    Basis Representation Theorem: Let [tex] k [/tex] be any integer larger than 1. Then, for each positive integer [tex] n [/tex], there exists a representation

    [tex] n = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s} [/tex]

    where [tex] a_{0} \neq 0 [/tex], and where each [tex] a_{i} [/tex] is nonnegative and less than [tex] k [/tex]. Furthermore, this representation of [tex] n [/tex] is unique; it is called the representation of [tex] n [/tex] to base [tex] k [/tex].

    Proof: Let [tex] b_{k}\left(n\right) [/tex] denote the number of representations of [tex] n [/tex] to the base [tex] k [/tex]. We must show that [tex] b_{k}\left(n\right) [/tex] always equals 1.

    Suppose that

    [tex] n = a_{0}k^{s} + a_{1}k^{s-1} + ... + a_{s-t}k^{t} [/tex]

    where neither [tex] a_{0} [/tex] nor [tex] a_{s-t} [/tex] equals zero. Then

    [tex] 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}[/tex]

    Thus we see that for each representation of [tex] n [/tex] to the base [tex] k [/tex], we can find a representation of [tex] n-1 [/tex]. Consequently,

    [tex] b_{k}\left(n\right) \leq b_{k}\left(n-1\right) [/tex]

    Question: In the previous line, why is there a "less than or equal to" sign rather than an "equal" or "greater than or equal to" sign?
  2. jcsd
  3. Dec 30, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    Each b_k representation has at least one associated b_k-1 representation, but there may be b_k-1 representations we don't know about. If there were U >= 0 such unknown representations (in fact U = 0, but we don't know that), then b_k + U = b_k-1, so b_k <= b_k-1.
  4. Dec 31, 2008 #3
    Thanks CRGreathouse.

    This is clear now. When first reading the proof, it seemed obvious that U = 0, but this was the flaw in my thinking. So we could use the "equals" sign but only if we first show that U = 0, which is more work than is necessary.
  5. Nov 5, 2009 #4


    User Avatar

    Thanks so much! This was really puzzling me too.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Proof: Basis Representation Theorem
  1. Basis Rep Theorem. (Replies: 6)