If $q=\dfrac{b}{2^n}$, show that $q$ has a finite binary expansion.

Question

Given the following statement,

Assume that $q=\dfrac{b}{2^n}$ for some $1\leq b<2^n$, where $b$ is an odd integer ($n$ is a positive integer).

I am to show that $q$ has a finite binary expansion $$q=\sum_{i=1}^{n} \frac{w_i}{2^i},$$ where $w_n=1$.

Although I plan to prove that $q$ has the binary expansion mentioned above, I have a question with regard to the meaning of the problem above:

Is the 'statement'

$q=\dfrac{b}{2^n}$ for some $1\leq b<2^n$ (with $b$ as an odd integer and $n$ as a positive integer); $q$ has a finite binary expansion where $w_n=1$

the same as

there exists $1\leq b<2^n$ such that $q=\dfrac{b}{2^n}$ (with $b$ as an odd integer and $n$ as a positive integer) and $q$ has a finite binary expansion where $w_n=1$

or is it the same as

for all $1\leq b<2^n$ such that $q=\dfrac{b}{2^n}$ (with $b$ as an odd integer and $n$ as a positive integer), $q$ has a finite binary expansion where $w_n=1$

I am confused as to the logic of the problem statement; any help in converting the problem statement to an expression with quantifiers or any help in clarifying the logic of the problem statement would be greatly appreciated.

Answer 1

The statement to prove is:

For all $q,b,n$ such that $b$ is odd, $n$ is a positive integer, $1\le b\le2^n$, and $q=\frac b{2^n}$, there exist binary digits $w_1,...,w_n$ such that $w_n=1$ and $q=\sum_{i=1}^{n} \frac{w_i}{2^i}$.

In situations like this, instead of stating the outermost "for all", we often think of the theorem as applying in a context that includes the relevant variables and hypotheses as constants and assumptions.

That is, instead of saying "Prove $\forall \vec x(P(\vec x)\implies Q(\vec x))$", we say "Assume $P(\vec x)$. Prove $Q(\vec x)$".

Also in your example, the desired conclusion doesn't mention $b$ or $n$ (although their existence is necessary for the proof). Note that the following are equivalent:

• $\forall q,b,n:(P(q,b,n)\implies R(q))$
• $\forall q((\exists b,n:P(q,b,n))\implies R(q))$

In any case, the proof amounts to assuming $P(q,b,n)$ and deriving $R(q)$.