You are not computing the parity correctly. In any symmetric group, the product of two even permutations is an even permutation (otherwise, $A_n$ would not be a subgroup!), the product of two odd permutations is an even permutation; and the product of two permutations of different parity is an odd permutation.
Instead, let's think about $S_3$, and how to embed it (or be unable to embed it) in $A_4$ and $A_5$.
$S_3 = \{\mathrm{Id}, (1\,2), (1\,3), (2\,3), (1\,2\,3), (1\,3\,2)\}.$ Now, $A_4$ doesn't have any subgroups of index $2$: they would be normal, and the only normal subgroups of $A_4$ are the trivial group, they whole group, and the subgroup $\{\mathrm{Id}, (1\,2)(3\,4), (1\,3)(2\,4), (1\,4)(2\,3)\}$ of index $3$. So $S_3$ cannot possibly embed into $A_4$.
What about $A_5$? There we have more leeway: there is no problem in mapping $(1\,2\,3)$ and $(1\,3\,2)$ to $A_5$: they have to map to $3$-cycles, so up to an automorphism of $A_5$ we may assume that we send $(1\,2\,3)$ to itself, and therefore $(1\,3\,2)$ to itself as well. We cannot just map $(1\,2)$ to itself, though: $(1\,2)\notin A_5$. However, we can "fix" the parity by multiplying by a single that won't mess up the action on $\{1,2,3\}$ (so that we still get that the product of the image of $(1\,2)$ and the image of $(1\,3)$ is $(1\,3\,2)$, as needed, since $(1\,2)(1\,3)=(1\,3\,2)$). Just take $(1\,2)(4\,5)$! Similarly, try sending $(1\,3)$ to $(1\,3)(4\,5)$, and $(2\,3)$ to $(2\,3)(4\,5)$. Check that everything works out.
You may have to do the small $n$ cases separately, but after $n=3$, it should be simple to see how to get this done.
Added. Moreover, since $S_n\hookrightarrow S_{n+1}$ (as the subgroup that fixes $n$), and this embedding necessarily respects parity, you have that $S_n$ embedds into $S_k$ for all $k\geq n$, and $A_n$ embeds into $A_{k}$ for all $k\geq n$. Added to the exercise, this shows that:
Proposition. Let $n$ be a positive integer. Then $S_n$ embeds into $A_k$ if and only if $n=1$ and $k$ is arbitrary; or $n\gt 1$ and $k\geq n+2$.
For your title question, the answer is "yes" (if $n\gt 1$, then $2n+1\gt n+2$; if $n=1$, then $S_n$ is trivial and embeds into every $A_n$, in particular into $A_{2}$, which is also trivial).
More interesting is the question of when $S_n$ embeds into $A_k$ as a maximal subgroup. The pairs $(n,k)$ with this property were completely characterized by Bret Benesh in A classification of certain maximal subgroups of alternating groups, in Computational Group Theory and the Theory of Groups, Contemporary Mathematics vol. 470, American Mathematical Society, pages 21-26.