Strong induction $n=2^a\cdot b$ [duplicate]

Given $n\in\mathbb N$, there exists a non-negative integer $a$ and an odd integer $b$ such that $n=2^a\cdot b$

Base Case: $n=1 =2^0\cdot1$

I.H: Assume its true for $n=1,2,\ldots,k$

How would i prove this?

Solution 1:

It's a rather straight forward induction.

Base Case : $n=1$ is odd.

$n = 2 = 2^1 \times 1$, if you want another.

Now, let $1,...,k$ be covered in the hypothesis. Look at $k+1$.

Either $k+1$ is odd or even. If it is odd, then $k+1 = 2^0 (k+1)$, where $k+1$ is odd (of course). Hence, we are done in this case.

If $k+1$ is even, then $\frac{k+1}{2} < k+1$ is an integer which has been covered in the inductive hypothesis, say $\frac{k+1}2 = 2^ab$, where $b$ is odd. Transposing, $k+1 = 2^{a+1}b$, where $b$ remains odd. Hence, $k+1$ can always be written in the desired form.

This completes the induction.

Solution 2:

Firstly note that this statament is reasonable: every number, odd or even could be written in this form. When $n$ is odd $a$ must be $0$. When $n$ is even $a \ge1$.

So, more formally: take an arbitrary $n \in \mathbb{N}$.

• If $n$ is odd we can say that $n=2^0n$
• If $n$ is even consider the prime factorization of $n$, $n=2^{\alpha_1}*3^{\alpha_2}*...*p_n^{\alpha_n}$ note that $ 2^{p_1}|n \space$ and $\space 2^{p_1+1} \not| n$ $\implies \exists b\in \mathbb{N}: n=2^{p_1}b$.

Solution 3:

In your comments you asked about how we could discover the proof I hinted at. The idea is simply that every natural $>0$ can be generated by repeatedly multiplying its odd part $\,\color{#c00}b\,$ by a power of $\,\color{#0a0}2.\,$ Said inductively: the set $\,S\,$ of naturals $> 0\,$ writable in form $\,\color{#0a0}2^a \color{#c00}b\,$ satisfies the following.

Lemma $ $ If $\,S\subseteq \Bbb N_{>0}$ contains all $\color{#c00}{\rm odds}$ and is closed under $\rm\color{#0a0}{multiplication\ by\ 2}\,$ then $\,S = \Bbb N_{>0}$

Proof $ $ Suppose for strong induction that $S$ contains every natural $< n.\,$ If $\,n\,$ is odd then $\,n\in S\,$ by $\rm\color{#c00}{hypothesis}$. Else $n = 2k\,$ for $k< n$ so $\,k\in S\,$ by induction, so $n = 2k\in S\,$ by $\rm\color{#0a0}{hypothesis}$.

Remark $ $ More generally, replacing $\,2\,$ by any natural $\,c > 1\,\,$ the same proof shows that any natural can be written uniquely in form $\,c^a b,\ c\nmid b\,$ and the above induction amounts to pulling out as many factors of $\,c\,$ as possible, i.e. until the remaining cofactor $\,b\,$ is no longer divisible by $\,c.\,$ Uniqueness is clear: if $\,c^ab = n = c^A d\,$ where, wlog $a < A,\,$ then $\,b = c^{A-a}d\Rightarrow c\mid b \,\Rightarrow\!\Leftarrow$

Beware $ $ If $\,c\,$ is not prime then the cofactor $b$ need not be coprime to $\,c\,$ so powers of $\,c\,$ need not combine additively under multiplication, e.g. for $\,c = 6\,$ we have $\,(6^2\cdot 2)(6^3\cdot 3) = 6^6\,$ so we get an extra power of $\,6\,$ from $\,bb' = 2\cdot 3,\,$ which can't occur for prime $\,c=p\,$ by $\,p\nmid b,b'\Rightarrow p\nmid bb'$ by Euclid's Lemma.

More generally see here, which shows how this is a special case of inductive generation of multiplicatively closed sets.