Q:

Solving $\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$

I have been solving this problem from Velleman's How to prove book:
$\{n^2 + n + 1 | n \in \mathbb{N} \} \subseteq \{2n + 1 | n \in \mathbb{N} \}$
This is my solution so far:
$\forall x (x \in \left\{n^2 + n + 1 \mid n \in \mathbb{N} \right\}) \implies (x \in \left\{2n + 1 \mid n \in \mathbb{N} \right\})$
$\forall x (\exists n \in \mathbb{N} (x = n^2 + n + 1)) \implies (\exists n \in \mathbb{N} (x=2n+1)) $
But the answer given in the book is:
$\forall n \in \mathbb{N}\exists m \in \mathbb{N}(n^2 + n + 1 = 2m + 1)$
I'm not able to understand how that answer is correct ?

A:

We may add some condiderations :
(i) from an "intuitive" point of view, it is easy to convince inself that the number $n^2 + n +1$, for all $n$ is odd; thus, it must be obviously true that :

$\{ n^2+n+1 | n \in \mathbb N \} \subseteq \{ 2m+1 | m \in \mathbb N \}$.

(ii) the defining condition for set inclusion is :

$A \subseteq B$ iff for all $x$, if $x \in A$, then $x \in A$;

in our example, this is :

forl all $x$, if $\exists n (x = n^2+n+1)$, then $\exists m (x = 2m+1)$.

Note : having rewritten the defining condition in explicit form (i.e. without the set-builder "operator" $\{ n | \varphi(n) \}$), we can verify that the variables $n,m$ are bound. Thus, it does not matter what variable we use, and using the same variable in both formulae can be misleading, because there is no "link" between the two.
(iii) now we can "formalize" the above facts with a single first-order formula expressing the condition for inclusion :

$\forall x(\exists n (x = n^2+n+1) \rightarrow \exists m (x = 2m+1))$ --- (*).

We can use some logical laws to transform the last formula.
We have that :

if $x$ does not occur free in $\alpha$, then $(∃x \beta → \alpha) ↔ ∀x(\beta → \alpha)$.

Thus, applying it to (*) [$n$ is not free in $\exists m (x = 2m+1)$], we get the equivalent formula :

$\forall x \forall n ((x = n^2+n+1) \rightarrow \exists m (x = 2m+1))$.

Now we use :

if $x$ does not occur free in $\alpha$, then $(\alpha → ∃x \beta) ↔ ∃x(\alpha → \beta)$.

Applying it to the above formula [$m$ is not free in $(x = n^2+n+1)$] we have :

$\forall x \forall n \exists m ((x = n^2+n+1) \rightarrow (x = 2m+1))$

which is again equivalent to (*).
The last transformation is licensed by identity laws :

if $x = a$ and $x = b$, then $a = b$.

Applying it to : $(x = n^2+n+1) \rightarrow ((x = 2m+1) \rightarrow (n^2+n+1 = 2m+1))$ we can get the final transformation of (*) :

$\forall n \exists m (n^2+n+1 = 2m+1)$.

