Prove the implication: $k$ is odd implies $k^n$ is odd So far, I have my base case where  $ k = 2n+1 $ and $k^n \equiv (2n+1)^n$. Plugging in $1$ for $n$ gives me $3$, which is odd so the base case is true.
Now for the inductive hypothesis: Assume $P(n)$ is true
I want to prove the implication $P(n)\implies P(n+1)$ via contraposition. So I would assume it is not the case $k^n$ is odd, so I assume $k^n$ is even. I would then rewrite $k^n=2l$ as it is equivalent to multiple of integer $l$.
I'm confused where to go from here though, so if someone can help me figure this out I would greatly appreciate it. Thank you!
 A: You can't assume that $k=2n+1$ with $n$ being the power with which you raise $k$: they have nothing to do with each other.
Instead, simply stick to $k$ being some arbitrary odd integer, and do induction on $n$
So, the base case is where $n=1$, i.e $k^n=k^1=k$ is odd. Check!
For the step: assume $k^n$ is odd, and now show that $k^{n+1}$ is odd. Again, all you need is that $k$ is odd. Indeed, no proof by contrapositive here needed either: this is going to be direct and fairly simple.
A: A notational note: you have $n$ as the exponent and in the representation of $k$, even though these do not need to be the same. So I will write $k=2m+1$. You do not need to use contraposition or anything fancy, just do straight induction on $n$ where $k$ is a fixed odd number.
For the induction step, you use the induction hypothesis which is that $k^n$ is odd, so $k^n=2m'+1$. Hence,
$$k^{n+1}=k^nk=(2m'+1)(2m+1)$$
Note, you will need to re-verify the base case using $k=2m+1$ and not $k=2n+1$ (although this is still trivial).
A: "About binomial theorem I am teeming with a lot of news."--from The Major General's Song, Pirates of Penzance, Gilbert and Sullivan.
It can also be done using the binomial theorem.
If $k$ is odd, we have
$k = 2j + 1, \tag 1$
for some $j \in \Bbb Z$. Then
$k^n = (2j + 1)^n = \displaystyle \sum_0^n \dfrac{n!}{i!(n - i)!}(2j)^i(1)^{(n - i)}; \tag 2$
inspection of (2) reveals that every term with $i \ne 0$ contains a factor of $2j$, hence is divisible by $2$.  The $i = 0$ term is precisely $1$, hence we have
$ \displaystyle \sum_0^n \dfrac{n!}{i!(n - i)!}(2k)^i(1)^{(n - i)} = 2m + 1 \tag 3$
for some $m \in \Bbb Z$, whence $k^n$ is in fact, like our friend the Modern Major General, odd.
Be assured that, though not at the forefront, induction is by no means left out of this argument; how else prove the binomial theorem?
A: Use the fundamental theorem of algebra. Any number n can be written as a product of primes $n = p_1p_2p_3...p_k$ where $p_i  \le p_{i+1}$
So if n is odd, 2 does not divide n, so $p_i \ne 2$  $\forall 0 \le i \le k$
So take $n^m$. $$n^m=p_1^m p_2^m...p_k^m \text{ where } p_i \ne 2  \forall 0 \le i \le k$$
So, 2 does not divide $n^m$
A: Another fancy proof using Bezout;
$k$ is odd $\iff\gcd(k,2)=1\iff \exists (u,v)\in\mathbb Z^2\mid uk+2v=1$
Let's consider the following induction relation $P(n): u^nk^n+2v\left(\sum\limits_{i=0}^{n-1} u^ik^i\right)=1$
$P(1)$ is true, as shown in the beginning.
Now assuming $P(n)$ then 
$1=u^nk^n+2v\left(\sum\limits_{i=0}^{n-1} u^ik^i\right)=u^nk^n\underbrace{(uk+2v)}_{=1}+2v\left(\sum\limits_{i=0}^{n-1} u^ik^i\right)=u^{n+1}k^{n+1}+2v\left(\sum\limits_{i=0}^{n} u^ik^i\right)$
So $P(n+1)$ is verified and the induction proof is completed.
Thus $\forall n\ge 1, \exists (a,b)\mid ak^n+2b=1\iff \gcd(k^n,2)=1\iff k^n\text{ is odd}$
