1. Limited time only! Sign up for a free 30min personal 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!

Proving that every non-negative integer can be expressed in binary

  1. Aug 11, 2013 #1
    I'm assuming this is a simple proof? I started thinking about it.

    It suffices to show that every even number can be written as positive powers of 2 (since every odd number is simply an even number plus 20). So let n = 2k for some non-negative integer k; we need to show that 2k = 2c1 + 4c2 + 8c3 + ... where each of c1, c2, c3 ... is 0 or 1.

    (Where do I go from here? Some sort of iterative scheme?)
     
  2. jcsd
  3. Aug 11, 2013 #2

    jbriggs444

    User Avatar
    Science Advisor

    Claim: Any non-negative integer i can be expressed in binary in no more than i+1 digits.

    Can you prove this claim with mathematical induction?
     
  4. Aug 11, 2013 #3
    Wow. I almost forgot about induction. I've been out of school for too long already lol.

    But is there any way to finish it the way I've started?
     
  5. Aug 11, 2013 #4

    jbriggs444

    User Avatar
    Science Advisor

    I think that what you are currently agonizing over is a way to prove a piece of the result:

    "If (c1, c2, c3, c4, ... cn) is the binary expansion of k then (c1, c2, c3, c4, ..., cn, 0 ) is the binary expansion of 2k"

    You could work at that and invoke the definition of a binary expansion, the distributive property of multiplication over addition and mathematical induction on the number of terms in the expansion and laboriously demonstrate that the result holds. Normally, though, that's the sort of thing that is obvious enough to be accepted without proof.

    Now, if you had a proof of the above claim (or are willing to accept it as obvious), can you come up with a similar claim that holds for odd numbers?

    If so, those are the two key pieces for the inductive proof that I have in mind.
     
    Last edited: Aug 11, 2013
  6. Aug 11, 2013 #5

    rcgldr

    User Avatar
    Homework Helper

    That should be positive multiples of 2.

    I'm not sure this is needed though, but I'm also not sure what constitutes "proof", without accepting some basic principles of math in any base, such as adding 1 to a number, in which case you could start with 0 and then repeatedly add 1 in base 2 to get any integer value.
     
  7. Aug 21, 2013 #6

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper

    I would proceed by induction. It holds for 1, so assume it holds for all integers less than r and try to prove it for r. find n such that 2^(n+1) > r ≥ 2^n. then r = 2^n + an error term less than 2^n which by inductive hypothesis can be expressed as a sum of powers of 2, with exponents less than n. done.


    this is just the principle of "grouping" used to teach kids arithmetic. I.e. you have a sequence of cardboard boxes, each twice the size of the previous one. You have a collection of bottles you need to box up. You just fill the largest box you can. Then with what is left over you again fill the largest box you can, which is smaller. continue...
     
  8. Aug 21, 2013 #7

    Mark44

    Staff: Mentor

    Is this what you meant to say? A nonnegative integer i can be expressed in way less than i+1 digits. For example, 9 can be expressed in only four binary digits as 1001.
     
  9. Aug 21, 2013 #8

    Nugatory

    User Avatar

    Staff: Mentor

    As long as "non-negative" was intended, it has to be phrased that way - zero requires one digit. (Of course that also loses the asymptotic logarithmic behavior, so I find the proposition somewhat uninteresting except as an exercise in proof by induction)
     
  10. Aug 22, 2013 #9

    jbriggs444

    User Avatar
    Science Advisor

    Yes, that is what I meant to say. It is not a tight upper bound, but all we need is an upper bound.
     
  11. Aug 22, 2013 #10

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    You can express it in i digits in base 1, and any other base will require less digits.
    In fact, you can express it in less than n digits in base b, where n satisfies ##i \le b^n##, i.e. ##n \ge \log_b(i)##.
    In particular, log29 ≈ 3.2 so 4 digits suffice.
     
  12. Aug 22, 2013 #11
    Let [itex]X= \{ n \in \mathbb Z_+: \enspace n \text{ can be expressed in binary}\}[/itex]. You want to show [itex]X=\mathbb Z_+[/itex]

    Try to prove the following lemma: If [itex]m,n\in X,[/itex] then [itex]m+n\in X[/itex]. Mathwonk's suggestion should give you a method of proof for the lemma.

    This may make your induction easier.

    (I'm not adding new content really... I'm just suggesting a way to organize your thoughts on this.)
     
  13. Aug 22, 2013 #12

    Mark44

    Staff: Mentor

    I don't believe that there is such a thing as base-1, but I get what you're saying. I.e., counting by tick-marks, where 4 = llll, and so on.

    In base-n, where n is a positive integer, there are n digits: 0, 1, ..., n-1. This means that in base-2, the digits are 0 and 1. If we follow the same pattern, base-1 would have only 1 digit, which would be 0.

    I had a long conversation with someone many (> 20) years ago on CompuServe, and he steadfastly maintained his belief in a base-1 system.
     
  14. Aug 27, 2013 #13
    Wow.
     
    Last edited: Aug 27, 2013
  15. Aug 27, 2013 #14
    I see.
     
  16. Sep 12, 2013 #15
    Ok, guys ... I'm starting to write out a formal proof but I'm having trouble finishing it off in an elegant way. It looks like it's gonna get messy trying to show that m + n equals a sum of powers of 2. Or am I missing some obvious, simple recipe?


    ekuSySe.png
     
  17. Sep 13, 2013 #16

    Nugatory

    User Avatar

    Staff: Mentor

    Instead of working with ##m+n##, you might try working with ##m+1##. If ##m## can be expressed in ##m## bits, how many bits worst case are required to express ##m+1##?
     
  18. Sep 13, 2013 #17
    m+1 worst case
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proving that every non-negative integer can be expressed in binary
  1. Non-Integer moduluses (Replies: 3)

Loading...