I think that the following proof of the fact that every subgroup of index $2$ of a given group is normal might count too. When I first came up with it (sometime during my sophomore year), I believed that I had just found the entrance to a royal road to mathematics.
Let $H\leq G$ be such that $[G:H]=2$. We'll prove that every right coset of $H$ is equal to a left coset of $H$.
Since $[G:H]=2$, $G$ is both the union of two disjoint right cosets of $H$ and the union of two disjoint left cosets of $H$. Let us suppose that $G=He \cup Hx = eH \cup yH$ where $x,y\in G\setminus H$ and $e$ denotes the identity element of $G$. According to standard lore regarding the symmetric difference of sets,
$He \cup Hx = He \triangle Hx \triangle (He \cap Hx) = He \triangle Hx \triangle \emptyset = H \triangle (Hx\triangle \emptyset) = H\triangle Hx$
and
$eH \cup yH = eH \triangle yH \triangle (eH \cap yH) = eH \triangle yH \triangle \emptyset = H \triangle (yH \triangle \emptyset) = H \triangle yH$.
Therefore, $H\triangle Hx = H\triangle yH$. Canceling $H$ on both sides of the latter equality—which is perfectly valid given that $(2^G, \triangle)$ is a group—we conclude that $Hx=yH$. Done.
If you consider that the prior argument doesn't qualify as awfully sophisticated, there is still another fancy way to derive the result in question. As a consequence of P. Hall's famous marriage theorem, M. Hall proves in Theorem 5.1.7 of his Combinatorial Theory that if $H$ is a finite index subgroup of $G$, there exists a set of elements that are simultaneously representatives for the right cosets of $H$ and the left cosets of $H$ (once he's proven the said theorem, he adds: "Simultaneous right-and-left coset representatives exist for a subgroup in a variety of other circumstances. This problem has been investigated by Ore 1."). In the case $[G:H]=2$, this implies at once that every right coset of $H$ is equal to a left coset of $H$ and we are done...
By the way, the Galois-theoretic proof of this exercise given by Matthias Künzer is just fabulous! Last but not least, ($[G:H]=2 \Rightarrow H \trianglelefteq G$) in the case when $|G|<\infty$ can also be seen a consequence of the well-known fact according to which any subgroup of a finite group whose index is equal to the smallest prime that divides the order of the group is of necessity a normal subgroup of the group (B. R. Gelbaum showcases in one of his books an action-free proof of this fact. He attributes both the fact and the action-free proof to Ernst G. Straus. Does any of you know on what grounds he did so? I have a Xerox copy of the relevant page in the book here. This exactly what Gelbaum writes therein: "At some time in the early 1940s Ernst G. Straus, sitting in a group theory class, saw the proof of the ... ... ... result [($[G:H]=2 \Rightarrow H \trianglelefteq G$)] ... and immediately conjectured (and proved that night): ... IF G:H [sic] IS THE SMALLEST PRIME DIVISOR P of #(G) THEN H IS A NORMAL SUBGROUP.").