I use the fact that $\mathbb{Z}[x]$ is a UFD. Lemma: if $HCF(a,b)=1$, $d(x)=HCF((x^{a}-1), (x^{b}-1))=x-1$. Proof: Direct application of Bezout's Lemma. We know that $(x^{a}-1)|(x^{ka}-1)$ for integral $k$, so we pick an integer $s$ such that $as=bt+1$ for some integer $t$, we get that $d(x)|(x^{bt+1}-1)$, $d(x)|(x^{bt}-1)$. Setting $(x-1)e(x)=d(x)$, $e(x)|x^{bt}, e(x)|x^{bt}-1$, implying that $e(x)=1$, proving the lemma. Cancelling the $x$s, it becomes \[P_{n,k}(x)=\frac{(x^{n}-1)(x^{n-1}-1)...(x^{n-k+1}-1)}{(x^{k}-1)(x^{k-1}-1)....(x-1)}\] It follows from the fact that $\binom{n}{k}$ is an integer that $k!|n(n-1)...(n-k+1)$. Applying the lemma and considering unique factorisation into irreducibles over the field of polynomials, this directly implies that the above function is a polynomial.