Can I use induction with increments higher than 1? Say I want to prove:

$a$ is odd $<=>$ $a^2$ is odd

However, instead of proving this in both directions, I want to show that this statement is true for all odd numbers.
Can I use induction with increments of 2 to get only the odd numbers? Does this require additional proof?
Is this proof correct?
Base: for $k=1$, $1$ is uneven and $1^2=1$ is odd.
Step: Assume the claim is true for some odd $k$, prove for $k+2$
Assumption: $k$ and $k^2$ are odd.
Proof:
1. $(k+2)^2 = k^2 + 4k + 4 = k^2 + 4(k+4)$
Since $k^2$ is odd, and $4(k+4)$ is even, then (odd+ even) = odd.
Therefore $(k+2)^2$ is odd.
2. $k+2$ = odd + even = odd
Therefore, $k+2$ is odd.
We have shown that $k+2$ is odd and $(k+2)^2$ is odd, completing the proof for all odd numbers.
 A: The axiom of induction doesn't let you do that directly, no.
But you can do the following: you make the claim (call it $P(k)$) that for every nonnegative integer $k$, $(2k+1)^2$ is odd.
$P(0)$ says that $1$ is odd, which is true.
If you suppose $P(k)$ is true, then you can show $P(k+1)$ is true using exactly your argument.
And then induction tells you that $P(k)$ is true for all integers $k \ge 0$.
====
You can also prove, using the axiom of induction, a little theorem, namely that...
If $H$ is a set of odd numbers containing $1$, and with the property that whenever $n \in H$, you also have $n+2 \in H$, then $H$ contains all positive odd numbers.
You can then apply this little theorem in doing the proof the way you wrote it in the first place.
In practice, any working mathematician would have no hesitation about writing your kind of proof, because the "little theorem" would be pretty obvious. But as you're learning, the obligations are stronger than when you've gained some expertise. :(
A: You can prove your statement by simple induction if you choose as induction predicate
$$
P(n) = n \mbox{ odd iff }  n^2 \mbox{ odd}
$$
which is equivalent to
$$
Q(n) = n \mbox{ even iff }  n^2 \mbox{ even}
$$
The base case $P(1)$ is the way you give it. (or you can start at $0$ and prove $Q(0))$.
In the recursion step, assume $P(n)$ and prove $P(n+1)$: both $(n+1)$ and $(n+1)^2$ have opposite parity of $n$ and $n^2$ respectively: in particular if $n^2$ was even, then $(n+1)^2 = n^2 + 2n +1$ is odd and viceversa.
So they both go from even to odd ($P(n)$ to $Q(n+1)$) or from odd to even ($Q(n)$ to $P(n+1)$).
