Some Random Notes

1.2 Fraction to Binary Conversion Proof

4 min read

Part 1: Mathematical Proof of the Fraction Conversion Algorithm

The Rule Explained

“Add the fraction to itself and retain the integer until the entire sequence becomes 0”

The Mathematical Foundation

Any fractional number (where ) can be uniquely represented in base-2 (binary) as a sum of negative powers of 2:

Expressed as an infinite series:

Where each digit is strictly either or .

Step 1: Multiply by 2 (Adding the fraction to itself)

Let’s multiply both sides of our series by :

Distributing the (which is ):

Step 2: Extracting the Integer and Remainder

Look closely at the resulting expression:

  1. is a standalone integer ( or ).
  2. The remaining parenthetical term is a new fractional value strictly less than (let’s call it ).

Therefore:

Since is multiplied by , the integer part of gives us our first binary digit ().

Step 3: Induction (Repeating the Process)

To find the next digit (), we take the fractional part and multiply it by 2:

Again, the integer part of this new product isolates . Repeating this loop recursively extracts , and so on, until the fractional remainder reaches (a terminating binary fraction) or repeats indefinitely (a repeating binary fraction like or ).

Q. How is the Remainder is Strictly Less Than 1

To prove that the remaining parenthetical term: is strictly less than 1, we can look at it through two mathematical lenses: place value geometry and a geometric series bound.

1. The Place Value Perspective (Binary Analogy)

Think about how fractional values work in base-10 first. If you have a decimal number like :

  • The tenths place () is less than .
  • The hundredths place () is less than .
  • The thousandths place () is less than .

No matter how many digits follow the decimal point, a fraction that starts immediately after the binary point (meaning it has no whole number integer part) represents a value smaller than 1.

In binary:

Since every term is either or , the absolute maximum possible value this infinite series can ever reach is if every single digit is equal to .

2. Mathematical Proof via Geometric Series

Let’s assume the worst-case scenario (the maximum possible sum) where every single coefficient equals :

This is a classic infinite geometric series where:

  • The first term
  • The common ratio

The formula for the sum of an infinite geometric series is:

Plugging in our values:

Conclusion

  • If every subsequent digit is , the infinite sum equals .
  • However, because it’s a fractional sequence representing a number strictly less than 1 to begin with (), it can never permanently equal 1 unless it terminates.
  • More importantly, because the first position of starts at (the place) without a leading whole-number integer, the value of is strictly bound between and ().

This guarantees that whenever you multiply by 2, the integer part you pull out is only the single most significant bit (), leaving a clean, valid fraction behind to repeat the process on!

Backlinks