Prove that an improper fraction with a finite binary expansion

[Jamin2112]

Homework Statement

I'm supposed to prove that an improper fraction with a finite binary expansion also can be written as a decimal.

Homework Equations

Obviously my fraction a/b, where a>b, will look like p₁/2¹ + p₂/2² + ... + p_n/2ⁿ

The Attempt at a Solution

And I have no idea where to go with this.

 

[hgfalling]

Can you write $\frac{1}{2^n}$ as a decimal for any n? Maybe try to do it by hand and see if there's a pattern. Then maybe use induction to formally establish that pattern.

 

[Jamin2112]

Can you write $\frac{1}{2^n}$ as a decimal for any n? Maybe try to do it by hand and see if there's a pattern. Then maybe use induction to formally establish that pattern.

1/2¹ = 1/2 = .5
1/2² = 1/4 = .25
1/2³ = 1/8 = .125
1/2⁴ = 1/16 = .0625
1/2⁵ = 1/32 = .03125
1/2⁶ = 1/64 = .015625
.
.
.
Hmmmm ... No pattern detected. Hint?

 

[hgfalling]

Are you going to get any non-terminating or repeating decimals out of this? Why or why not?

 

[Jamin2112]

Are you going to get any non-terminating or repeating decimals out of this? Why or why not?

Since the last digit is 5, and 5/2 is a decimal, you will always be able to get a decimal answer.

 

[hgfalling]

OK, so now you have a number with a finite binary representation (ie coefficients of negative powers of 2). And you have terminating decimals for each negative power of 2. Prove that you have won. :)

 

[Jamin2112]

OK, so now you have a number with a finite binary representation (ie coefficients of negative powers of 2). And you have terminating decimals for each negative power of 2. Prove that you have won. :)

I'll take a shot at it.

Proof:

An improper fraction can be represented a/b, where a < b, and a, b $$\in$$ $$Z$$. Suppose a/b can be represented as a finite binary expansion. Then a/b = m₁/2¹ + m₂/2² + m₃/2³ + ... + m_n/2ⁿ.

Where should I go from here? Hence a/b = $$\delta$$₁/10¹ + $$\delta$$₂/10² + $$\delta$$₃/10³ + ... + $$\delta$$_k/10^k.

 

[hgfalling]

OK, so now you need the $\delta_i$ values.

So suppose I give you 1011.101 in binary. Can you convert it to decimal?

 

[HallsofIvy]

I presume you mean can be written as a finite decimal expansion- any number can be "written as a decimal". A number can be written as a finite binary expansion if and only if it is a fraction that, reduced to lowest form, has a power of 2 as denominator. A number can be written as a finite decimal expansion if and only if it is a fraction that, reduce to lowest form, has denominator which is a product of powers of 2 and 5 only.

 

[Jamin2112]

OK, so now you need the $\delta_i$ values.

So suppose I give you 1011.101 in binary. Can you convert it to decimal?

Sure.

(1x2³)+(0x2²)+(1x2¹)+(1x2⁰)+(1x2^-1)+(0x2^-2)+(1x2^-3) = 8 + 0 + 2 + 1 + 1/2 + 0 + 1/8 = 11 ⁵/₈ = 11.625.

All that matters is how I went about making the (1/2 + 0 + 1/8) into a decimal, i.e., I need to show that 100/2, 100/4, 100/8, 100/16, ... are decimals. I suppose some sort of induction would be necessary. My statement P(n): for all integers n≥1, 100/2ⁿ is a rational number. Proof. We use induction on n. If n=1, then 100/2ⁿ=100/2¹, a rational number. Thus the base case holds. Now we wish to show that if 100/2ⁿ is a rational number, then 100/2ⁿ⁺¹ is a rational number. 100/2ⁿ is converted to 100/2ⁿ⁺¹ simply by dividing by 2. Because halving a rational yields another rational number, 100/2ⁿ is a rational number for all n.

Something like that?

 

[Jamin2112]

I presume you mean can be written as a finite decimal expansion- any number can be "written as a decimal". A number can be written as a finite binary expansion if and only if it is a fraction that, reduced to lowest form, has a power of 2 as denominator. A number can be written as a finite decimal expansion if and only if it is a fraction that, reduce to lowest form, has denominator which is a product of powers of 2 and 5 only.

I'm supposed to prove that an improper fraction that can be represented with a finite binary expansion can also be written as a decimal (a base 10 expansion, in other words), but not the converse (show that not all finite base 10 expansions have finite base 2 expansions)

 

[Jamin2112]

So ...

1/2¹ = .5 -----
1/2² = .25 -----
1/2³ = .125 ----- ends in 125
1/2⁴ = .0625 ----- ends in 625
1/2⁵ = .03125 ----- ends in 125
1/2⁶ = .0015625 ----- ends in 625
1/2⁷ = .00078125 ----- ends in 125
1/2⁸ =.00390625 ----- ends in 625
1/2⁹=.001953125 ----- ends in 125


That's the only patter I can detect: the last 3 digits alternate between 125 and 625.

 

[HallsofIvy]

As I said before, the numbers that can be written as a finite decimal expansion are those rational numbers which, reduced to lowest form, have denominators powers of 2 and 5. A number will have a finite binary expansion if and only if it can be written as a fraction with denominator a power of 2 only.

Obviously if $x= \frac{m}{2^n}$ then it can be written as $x= \frac{m}{2^n5^0}$. 1/5= 0.2 has a finite decimal expansion but its denominator is not a power of 2 and so cannot be written as a finite binary expansion.