Negation of quantifiers

Prove the following statement on negation of quantifiers:

Statement: To negate a statement of the form
Q_1x_1 Q_2x_2 \ldots Q_nx_n\; P(x_1,x_2,\ldots,x_n),
where $Q_i$ is $\forall$ or $\exists$ for $1 \leq i \leq n$, we do the following:

(i) Change every $\forall$ to $\exists$ and every $\exists$ into $\forall$.

(ii) Replace $P$ by its negation.

Background: This problem appears in the book How to Think Like a Mathematician by Kevin Houston, where it comes up in a chapter with an introduction to induction. I remember spending considerable time on this problem and not being able to come up with anything satisfactory. It seemed like you had to go into some deep logic to try to come up with an answer (something the author did not intend). I communicated with the author and noted the exercise, but he never got back to me. I took this as a sign that the exercise was flawed (or at least was very inappropriate for where it was placed in the text). I am still curious as to how this problem may be solved, if at all possible. Or is it something more axiomatic in nature and not something you can really deduce per se?

Solutions Collecting From Web of "Negation of quantifiers"