Using induction to prove that the infinite set of polynomials is countably infinite Let $P_n$ be the set of all polynomials of degree n with integer coefficients. Prove that $P_n$ is countable.
So I know to prove that $P_n$ is countable, it must be either infinitely countable or finite. Since we know it's not a finite set, it must be infinitely countable. Therefore, I need to prove that the set of all polynomials is equivalent to the set of natural numbers. This would imply that I need to use induction. My book provides a solution, but I don't really understand it. Can someone provide me with some insight on how to think about this problem?
The book says to set $$ P_n= n + a_0x^n + a_1x^{n-1} +a_2x^{n-2}+\cdots+a_n$$
and this is the part I get lost at,
let $$h = n+ a_0 + [a_1] + [a_2]+\cdots+[a_n]$$
They then note $h\ge1$ and each $\lvert a_i \rvert \le h$
After that I'm absolutely confused how they use induction to provide a proof. Please help!
 A: Note that $P_n$ is isomorphic to $\Bbb Z^{n+1}$ via the correspondence
$$(a_0,a_1,\dots,a_n)\in\Bbb Z^{n+1}\iff a_0+a_1x+\dots+a_nx^n\in P_n,$$
so it is sufficient to prove that $\Bbb Z^{n+1}$ is countably infinite. The easy way to do this is to find an injection from $\Bbb Z^{n+1}$ to $\Bbb N$, since $\Bbb Z^{n+1}$ is clearly not finite, and
$$f(a_0,a_1,\dots,a_n)=p_1^{g(a_0)}p_2^{g(a_1)}\dots p_{n+1}^{g(a_n)}$$
will do the trick (where $p_n$ is the $n$th prime, and $g(n)=2n^2+n$ is an injection $\Bbb Z\to\Bbb N$).
A: The trick is to see that
$h = n+ |a_0| + |a_1| + |a_2|+\cdots+|a_n|$ ($a_n \ne 0,$ $n \ge 1$)
yields a class of polynomial for each $h.$
$h = 2$ has the solutions: $ n =1$,  $a_1 = 1$ which yields the polynomial
$x$
$h=3$ has  solutions:
$n =2$, $a_2 =\pm1 $ which yields the polynomials $x^2$ and $-x^2$
$n =1$, $a_1 =\pm$ which yields $2x$ and $-2x$,
$n =1$, $a_1 =\pm1$, $a_0 = \pm1$ which yields $x +1 $, $x -1$, $-x +1$, and $-x - 1$.
and so on.
For each $h,$ there are finite polynomials yield and for all $h$ all polynomials will be yielded.  Thus we have a countable union of finite sets of polynomials.  Thus there are countably many polynomials.
