Let $n$ be a positive integer. Show that every integer $m$ with $ 1 \leq m \leq 2n $ can be expressed as $2^pk$, where $p$ is a nonnegative integer and $k$ is an odd integer with $1 \leq k < 2n$.
I wrote out some $m$ to try to conceive the proof. I observed:
$\bbox[5px,border:1px solid grey]{\text{Case 1: $m$ odd}}$ Odd numbers $\neq 2p$, thus the only choice is to put $p = 0$ and $k = m$.
$\bbox[5px,border:1px solid grey]{\text{Case 2: $m$ even and power of 2}}$ Then $p$ can be determined by division or inspection to "square with" the power of $2$. This requires $k = 1$. Is an explicit formula for $p$ necessary?
$\bbox[5px,border:1px solid grey]{\text{Case 3: $m$ even and NOT A power of 2}}$
$\begin{array}{cc}
\\
\boxed{m = 6}: 6 = 2^1 \cdot 3 \qquad \qquad & \boxed{m = 10}: 10 = 2^1 \cdot 5 \qquad \qquad & \boxed{m = 12}: 12 = 2^2 \cdot 3 \\
\boxed{m = 14}: 14 = 2 \cdot 7 \qquad \qquad & \boxed{m = 18}: 18 = 2^1 \cdot 9 \qquad \qquad & \boxed{m = 20}: 20 = 2^2 \cdot 5\\
\boxed{m = 22}: 22 = 2 \cdot 11 \qquad \qquad & \boxed{m = 24}: 24 = 2^3 \cdot 3 \qquad \qquad & \boxed{m = 26}: 26 = 2^1 \cdot 13
\end{array}$
Solution's Proof by Contradiction: $\color{#0073CF}{\Large{\mathbb{[}}}$Let $p$ be the greatest nonnegative integer
such that $2^p | m. \color{#0073CF}{\Large{\text{]}}}$ $\color{red}{\Large{\text{[}}}$ Then $m= 2^pk$ for some positive integer $k$. Necessarily $k$ is odd,
for otherwise this would contradicts the definition of $p$. $\color{red}{\Large{\text{]}}}$
$\Large{\text{1.}}$ Could someone please expound on the answer? It differs from my work above?
$\Large{\text{2.}}$ Is there a general formula/pattern for Case $3$?
I referenced 1. Source: Exercise 5.42(a), P125 of Mathematical Proofs, 2nd ed. by Chartrand et al
Best Answer
I am not sure, what you are looking for as the proof is fine, but here are some alternatives: