Main Page

From ProofWiki

Jump to: navigation, search
Welcome to ProofWiki, the online compendium of mathematical proofs. Log in or create an account to contribute!

Welcome to ProofWiki!

Welcome to ProofWiki.org! ProofWiki is an online compendium of mathematical proofs! Our goal is the collection, collaboration and classification of mathematical proofs. If you are interested in helping create an online resource for math proofs feel free to Create an account and contribute! Thanks and enjoy!

If you have any questions, comments, or suggestions please contact webmaster at proofwiki.org , post on the discussion page, or contact one of the ProofWiki sysops. To see what's currently happening in the ProofWiki community, visit the community portal.


Proof Index ~ Definitions ~ Sandbox


Site Statistics
Proofs:2,299
Definitions:1,658
Users:185
Quick Tips

Latest Proof: Quotient and Remainder to Number Base on 5 February 2010 by Matt Westwood

Top 10 Wanted Proofs

Want to do something different? Check here for articles linked to but not created, or finish a stub article.

News

December 26, 2009

  • We are back to the user only editing policy due to a bot attack yesterday. Until we can figure something else out this is how it will have to be. --Joe (talk)

December 24, 2009

  • Articles can now be created and edited by anyone, no need to log in or create an account unless you want to. --Joe (talk)

July 6, 2009

June 28, 2009

June 17, 2009

  • Over 1000 definitions! It's a banner month for ProofWiki it seems! --Cynic (talk)

June 15, 2009

  • Upgraded site software to newest version (1.15.0) --Joe (talk)

June 6, 2009

February 13, 2009

January 25, 2009

December 25, 2008

  • ProofWiki would like to wish you all a Merry Christmas! (And a happy Taiwanese Constitution Day for all the non-Christians) --Cynic-----(talk)

November 2, 2008

October 19, 2008

  • Added new buttons to the editing toolbar. So far it's only two, but I hope to expand to have some more useful ones. In order to see them you may have to clear your browsers cache. To do this in firefox press Crtl+R. If anyone has suggestions for new buttons let me know.--Joe
Show All News


Proof of the Week

Basis Representation Theorem


Theorem

Let b \in \Z: b > 1.


For every n \in \Z_+, there exists one and only one sequence \left \langle {r_k} \right \rangle_{0 \le k \le m} such that:

  1. n = \sum_{j = 0}^k r_j b^j;
  2. \forall j \in \left[{0 \, . \, . \, k}\right]: r_j \in \N_b;
  3. r_k \ne 0.


This unique sequence is called the representation of n to the base b, or, informally, we can say n is (written) in base b.


Proof

Let s_b \left({n}\right) be the number of ways of representing n to the base b.

We need to show that s_b \left({n}\right) = 1 always.


Now, it is possible that some of the ri = 0 in a particular representation. So we may exclude these terms, and it won't affect the representation.


So, suppose:

n = r_k b^k + r_{k-1} b^{k-1} + \cdots + r_t b^t

where r_k \ne 0, r_t \ne 0.


Then:

n − 1 = r_k b^k + r_{k - 1} b^{k - 1} + \cdots + r_t b^t - 1                    
= r_k b^k + r_{k - 1} b^{k - 1} + \cdots + \left({r_t - 1}\right) b^t + b^t - 1                    
= r_k b^k + r_{k - 1} b^{k - 1} + \cdots + \left({r_t - 1}\right) b^t + \sum_{j = 0}^{t - 1} {\left({b - 1}\right) b^j}          Sum of Geometric Progression          


from the identity \sum_{j = 0}^{n - 1} x^j = {\frac {x^n - 1} {x - 1}}, x \ne 1.


Note that we have already specified that b > 1.

So for each representation of n to the base b, we can find a representation of n − 1.

If n has another representation to the base b, then the same procedure will generate a new representation of n − 1. Thus s_b \left({n}\right) \le s_b \left({n - 1}\right).


Note that this holds even if n has no representation at all, because if this is the case, then s_b \left({n}\right) = 0 \le s_b \left({n - 1}\right).


So this inequality implies the following:

\forall m, n: s_b \left({m}\right) \le s_b \left({m - 1}\right) \le \ldots \le s_b \left({n + 1}\right) \le s_b \left({n}\right)


From N less than M to the N‎ and the fact that bn has at least one representation (itself), we see:

1 \le s_b \left({b^n}\right) \le s_b \left({n}\right) \le s_b \left({1}\right) = 1


The entries at either end of this inequality are 1, so all the intermediate entries must also be 1.

So s_b \left({n}\right) = 1 and the theorem has been proved.

\blacksquare


Comment

So, once we have chosen a base b > 1, we can express any positive integer n uniquely as:

n = \sum_{j = 0}^k {r_j b^j}: r_0, r_1, \ldots, r_k \in \left\{{0, 1, \ldots, b-1}\right\}


Then we can write n = \sum_{j = 0}^m {r_j b^j} as:

\left[{r_m r_{m-1} \ldots r_2 r_1 r_0}\right]_b


Personal tools