Prove that an odd integer is always of the form $2m+1$

Question

I have that by definition an integer $n$ is even if $n = 2m$ for some integer $m$. By definition an integer is odd if it is not even. I would like to prove that if $n$ is odd, then $n = 2m + 1$ for some $m$.

I am supposed to show this using at little as possible about the properties of the integers. I don't, for example, know anything about division algorithms like Euclidean division.

I can show that all numbers of the form $2m + 1$ are odd, but how can I show that all integers that are odd are indeed of this form?

Answer 1

Let $n$ be odd, i.e. an integer that is not even. Let $k$ be the largest even integer less than or equal to $n$. Since $k$ is even there is some integer $m$ with $k=2m$. Consider $n-k$, an integer (because it is the difference of two integers). It is nonnegative, because $k\le n$. It is not zero, since otherwise $k=n$ and then $n$ would be even. If $n-k\ge 2$, then $n\ge k+2$ and hence $k+2$ would be larger than $k$, less than or equal to $n$, and even. [Proof: $k+2=2m+2=2(m+1)$.] This contradicts the choice of $k$, so is impossible.

The only integer that is greater than zero and less than two is one. Hence $n-k=1$, so $n=k+1=2m+1$ for some integer $m$, as desired.

Answer 2

If you know the division algorithm (theorem), then every integer can be written in the form $2m+r$ where $m,r$ are integers and $0\le r<2$. I.e. as $2m$ or as $2m+1$. By this result, the integers that are odd are not of the form $2m$ and hence of the form $2m+1$.

Answer 3

induction on odd integers

prove
$n\in Z$ is odd $\Rightarrow\exists_{m\in Z}{n=2m+1}$

base case of $n=1:1=2(0)+1$. assume true for all n: $n=2m+1$. next odd number is $n+2=2m+1+2=2(m+1)+1$

it holds for all $0 \le n$ odd $\in Z$ by induction