Let p be the boolean value for the statement "$n^3+2^n+1$ is odd", q be the boolean value for "n is even".
$$p \rightarrow q$$
$$1 \rightarrow 1$$ $$0 \rightarrow 1$$ $$0 \rightarrow 0$$
(as you can see, only $1 \rightarrow 0$ will indicate $p \rightarrow q$ is false)
The contrapositive of $p \rightarrow q$ is $\lnot q \rightarrow \lnot p$, which is "if n is not even, $n^3+2^n+1$ is not odd."
The statement "if $n^3+2n+1$ is even then n is odd" is implying $\lnot p \rightarrow \lnot q$ and it is not equivalent to $p → q$.
$$¬p → ¬q$$
$$¬0 → ¬0$$ $$¬1 → ¬0$$ $$¬1 → ¬1$$
($\lnot p \rightarrow \lnot q$ will still be valid when $p=1$ and $q=0$, which is not the case in $p \rightarrow q$)
If it works for the contrapositive, your statement definitely holds.
The statements $p \rightarrow q$ and $\lnot q \rightarrow \lnot p$ are logically equivalent.
Contraposition is often helpful when an implication has multiple hypotheses, or when the hypothesis specifies multiple objects (perhaps infinitely many).
As a simple (and arguably artificial) example, compare, for $x$ a real number:
1(a). If $x^4 - x^3 + x^2 \neq 1$, then $x \neq 1$. (Not easy to see without implicit contraposition?)
1(b). If $x = 1$, then $x^4 - x^3 + x^2 = 1$. (Immediately obvious.)
Here's a classic from elementary real analysis, with $x$ again standing for a real number:
2(a). If $|x| \leq \frac{1}{n}$ for every positive integer $n$, then $x = 0$.
This is true, but awkward to prove directly because there are effectively infinitely many hypotheses (one for each positive $n$), yet no finite number of these hypotheses implies the conclusion.
2(b). If $x \neq 0$, there exists a positive integer $n$ such that $\frac{1}{n} < |x|$.
The contrapositive, which follows immediately from the Archimedean property, requires only a strategy for showing some hypothesis is violated if the conclusion is false.
3(a). If $f$ is a continuous, real-valued function on $[0, 1]$ and if
$$
\int_0^1 f(x) g(x)\, dx = 0\quad\text{for every continuous $g$,}
$$
then $f \equiv 0$.
3(b). If $f$ is a continuous, real-valued function on $[0, 1]$ that is not indentically zero, then
$$
\int_0^1 f(x) g(x)\, dx \neq 0\quad\text{for some continuous $g$.}
$$
Here contraposition is not especially helpful because the specific choice $f = g$ gives either direction. That is, 3(a) has infinitely many hypotheses, but one of them is sufficient to deduce the conclusion.
Contrast with the superficially similar-looking:
4(a). If $f$ is a continuous, real-valued function on $[0, 1]$ and if
$$
\int_0^1 f(x) g(x)\, dx = 0\quad\text{for every non-negative step function $g$,}
$$
then $f \equiv 0$.
4(b). If $f$ is a continuous, real-valued function on $[0, 1]$ that is not indentically zero, then
$$
\int_0^1 f(x) g(x)\, dx \neq 0\quad\text{for some non-negative step function $g$.}
$$
(Sketch of 4(b): If $f$ is not identically $0$, there is an $x_0$ in $(0, 1)$ such that $f(x_0) \neq 0$. By continuity, there exists a $\delta > 0$ such that $[x_0 - \delta, x_0 + \delta] \subset (0, 1)$ and $|f(x)| > |f(x_0)|/2$ for all $x$ with $|x - x_0| < \delta$. Let $g$ be the characteristic function of $[x_0 - \delta, x_0 + \delta]$.)
As in 2(a), the hypothesis of 4(a) comprises infinitely many conditions, and no finite number suffice. Here, the contrapositive 4(b) arises naturally, because in trying to establish 4(a) directly one is all but forced to ask how the conclusion could fail.
Best Answer
The contrapositive to a statement "$P$ implies $Q$" is "not $Q$ implies not $P$". Symbolically,
$$(P \implies Q) \iff (\neg Q \implies \neg P)$$
That is, you not only assume the negation but you effectively swap around what implies what.
Thus, if you are trying to prove "if $n$ is an integer with $n^2$ odd, then $n$ is odd", then the contrapositive is "if $n$ is an even integer, then $n^2$ is even." This is basically what you said, but notice how it is a little more nuanced than simply negating the statement. (Above, $P$ can be taken as "$n^2$ is odd" and $Q$ as "$n$ is odd.")
To prove this statement, you can thus indeed say $n=2k$ for some integer $k$, and then show $2$ divides $n^2$, making it even. This follows quite easily, as...