Prove that a power of odd number is always odd by induction.

Question

The problem has confused me for like half hour.

An integer is odd if it can be written as $d = 2m+1$. Use induction to prove that the ${d^n} = 1 \pmod2$

by induction, the basecase is pretty simple , let $n = 0$ then ${d^0}=1 \pmod2$ is correct. But I stucked in the I.H and inductive steps.

Any hints please?

Thank you in advance!

Answer 1

So you assume true up to an arbitrary integer $k$ (the Inductive Hypothesis), then prove true for the $k+1$ case.

So consider $d^{k} \equiv 1 \pmod 2$. So what happens when you multiply both sides by $d?$ You get $d^{k} * d \equiv d \pmod 2$. As $d$ is odd by the Inductive Hypothesis, we get that $d^{k+1}$ is also odd.

Alternatively, you can look at this combinatorially as well. So

$$(2m+1)^{k} = (2m+1)(2m+1)...(2m+1) = \prod_{i=1}^{k} (2m+1)$$

By expanding, the last digit will always be $1$. And every other term will be multiplied by $2m$, which implies that every other term is even. We know the even numbers are closed under addition, we have an integer of the form

$$2x + 1 = \sum_{i=0}^{k} \binom{k}{i} (2m)^{i} * 1^{k-i}$$

Answer 2

Your I.H. is that $d^n \equiv 1 \mod 2$. Then $d^{n+1} = d^n(2m+1) = 2md^n + d^n \equiv d^n \mod 2 \equiv 1 \mod 2$ by the induction hypothesis.

Answer 3

It's easier to just show that the product of a finite number of odd integers is odd. This can be done inductively if you like. Then your problem is a special case of this.

Base case: a single odd number is odd.

Inductive step: Assume $n_1,n_2,\ldots,n_{k+1}$ are odd and that $p_k = (n_1)(n_2)\cdots(n_k)$ is odd. Then $n_{k+1}=2a+1$ and $p_k=2b+1$ for some integers $a,b$. Thus $p_{k+1}=p_kn_{k+1}=(2a+1)(2b+1)=4ab+2a+2b+1=2(2ab+a+b)+1$ is odd.

Hence the product of a finite number of odd integers is odd, and in particular $(2a+1)^k$ is odd for integral $a$ and positive integral $k$.

Answer 4

Hint $\ $ Specialize $\,S =$ odds $ $ in the following

Theorem $\ $ Let $\,S\,$ be a set of integers $ $ closed under multiplication: $\,n,m\in S\,\Rightarrow\, nm \in S.\,$
Suppose $\,a\in S.\,$ Then $\ a^n\in S\ $ for all integers $\,n\ge 1.\,$

Proof $\ $ By induction on $\,n.\,$ The base case $\,n=1\,$ is true by hypothesis: $\,a^1 = a\in S.\,$ If $\,a^n \in S\,$ then $\,a(a^n) = a^{n+1}\in S\,$ since $\,S\,$ is closed under multiplication, completing the induction.