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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook