Strong induction $n=2^a\cdot b$ 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?
 A: 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.
A: 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$.

A: In your comments you inquired how we could discover the proof that I hinted. 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 $\rm\color{#90f}{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.\,$ $\rm\color{#90f}{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$
More generally see here, which shows how this is a special case of inductive generation of multiplicatively closed sets (here uniqueness may fail).
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.
