The number of subgroups of index two in $G$
Not as easy as I first thought!
Let $H_1,...,H_k$ be all the distinct index two subgroups of $G$. Let $H = H_1 \cap ... \cap H_k$. We claim that $G^2 \subset H$.
Indeed, if $x^2 \in G^2$ then for any $H_i$, we have three cosets $H_i,xH_i,x^2H_i$ in $G$, of which two must coincide. From here, $x^2 \in H_i$ is an immediate conclusion, and therefore $x^2 \in H$.
Thus, $G^2$, already being normal in $G$, is normal in $H_i$ for each $i$. Let $J_i = \frac {H_i}{G^2}$. This is a subgroup of $\frac{G}{G^2}$ of index $2$, as can be easily checked.
Furthermore, it is not difficult to check that every subgroup of index $2$ of $G/G^2$ is of the form $H_i/G^2$ for some $i$ : indeed, let $J$ be a subgroup of $G/G^2$ and let $L = \{x \in G : xG^2 \in J\}$ and one checks that $L$ is of index $2$ in $G$.
Thus, we have a one-one correspondence between the number of subgroups of index $2$ in $G$, and of index $2$ in $G/G^2$.
However, $G/G^2$ is seen to have structure. For example, it is abelian. However, more can be said : note that for all $x \in G/G^2$, we have $x^2= e$. Thus, by the fundamental theorem of abelian groups, the decomposition of $G/G^2$ can only contain factors of $\mathbb Z_2$. More precisely, it follows that $G/G^2 \cong \oplus_{i=1}^n \mathbb Z_2$.
So we come down to this vector space, and checking its index two subgroups.
First, we note that the index two subgroups of $G/G^2$ in fact match with the $n-1$ dimensional hyperplanes of the vector space $\oplus_{i=1}^n \mathbb Z_2$. To see this, note that any $n-1$ dimensional hyperplane is by definition a subgroup under addition and also has index $2$. Conversely, the image of any subgroup of index $2$ is closed under scalar multiplication (there are only two scalars $0,1$ so this is obvious) and addition , so is a subspace.
Thus, we are down to counting the number of $n-1$ dimensional hyperplanes of an $n$ dimensional space over $\mathbb Z_2$.
We do this as follows : first, find the number of $n-1$ sized linearly independent subsets of $\mathbb Z_2^n$. Then, some of these might generate the same hyperplane, so we combine those generating the same hyperplane to get the answer. That is, the answer should be : "number of linearly independent $n-1$ subsets / number of bases of an $n-1$ dimensional hyperplane".
Let us start with the first part. We have to choose $\{v_1,...,v_{n-1}\}$ linearly independent. We can choose $v_1$ to be anything but $0$,so in $2^{n} - 1$ ways. We can choose $v_2$ to be anything but in the span of $v_1$ which has two elements, so $2^{n} - 2$ ways.For $k \leq n-2$, We can choose $v_{k+1}$ not in the span of $v_{1},...,v_{k}$(which has $2^{k}$ elements) in $2^n -2^k$ ways. Thus, the total number of such linearly independent subsets comes out to be $(2^{n} - 1)(2^{n} - 2) \cdots (2^{n} - 2^{n-2})$.
Now, how many bases does an $n-1$ dimensional hyperplane have? An $n-1$ dimensional hyperplane is as good as $\mathbb Z_2^{n-1}$ for the above argument. Thus, we get by repeating the above argument for this space, that there are $(2^{n-1} - 1) ... (2^{n-1} - 2^{n-2})$ bases for any given $n-1$ dimensional hyperplane.
Whence the answer is given by : $$ \frac{(2^n - 1)(2^{n} - 2) ... (2^{n} - 2^{n-2})}{(2^{n-1} - 1) ... (2^{n-1} - 2^{n-2})} = 2^n - 1 = [G:G^2] - 1 $$
from which we conclude.
Corollaries :
A group has no subgroup of index $2$ if and only if it is generated by squares.
A group has a unique subgroup of index $2$ if and only if $G^2$ is of index $2$ in $G$.
$A_n$ has no subgroups of index $2$ and $S_n$ has a unique index two subgroup namely $A_n$.