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

[Jamin2112]

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 2⁰). So let n = 2k for some non-negative integer k; we need to show that 2k = 2c₁ + 4c₂ + 8c₃ + ... where each of c₁, c₂, c₃ ... is 0 or 1.

(Where do I go from here? Some sort of iterative scheme?)

 

[jbriggs444]

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?

 

[Jamin2112]

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?

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?

 

[jbriggs444]

But is there any way to finish it the way I've started?

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.

 

[rcgldr]

It suffices to show that every even number can be written as positive powers of 2 ...

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.

 

[mathwonk]

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...

 

[Mark44]

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

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.

 

[Nugatory]

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.

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)

 

[jbriggs444]

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.

Yes, that is what I meant to say. It is not a tight upper bound, but all we need is an upper bound.

 

[CompuChip]

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, log₂9 ≈ 3.2 so 4 digits suffice.

 

[economicsnerd]

Let X= \{ n \in \mathbb Z_+: \enspace n \text{ can be expressed in binary}\}. You want to show X=\mathbb Z_+

Try to prove the following lemma: If m,n\in X, then m+n\in X. 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.)

 

[Mark44]

You can express it in i digits in base 1

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.

, 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, log₂9 ≈ 3.2 so 4 digits suffice.

 

[Jamin2112]

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.

Wow.

 

[Jamin2112]

Let X= \{ n \in \mathbb Z_+: \enspace n \text{ can be expressed in binary}\}. You want to show X=\mathbb Z_+

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

I see.

 

[Jamin2112]

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 going to get messy trying to show that m + n equals a sum of powers of 2. Or am I missing some obvious, simple recipe?

 

[Nugatory]

Or am I missing some obvious, simple recipe?

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$?

 

[Jamin2112]

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$?

m+1 worst case