An Unusual "Polynomial Identity" For a positive integer $q$ define a sequence of polynomial as follows:
$$\begin{align}
p_0(q)&\equiv1\\
p_1(q)&\equiv0\\
p_n(q)&=q^n-\sum_{k=1}^n{k+q-1\choose k}p_{n-k}(q),\ n\geq2
\end{align}$$
Experimentation suggests that $$p_n(q)=(q-1)^qq^{n-q},\text{ for }n\geq q$$
I stumbled on this while trying to solve this problem on the probability that a randomly selected polynomial in a field with $q$ elements has no roots in the field.  I wanted to figure out what the answer would be, so I counted the non-vanishing monic polynomials by subtracting the number of polynomials with a root.  An $n$th-degree polynomial with a root is a product of $k>0$ terms of the form $(q-a)$ times a non-vanishing polynomial of degree $n-k,$ which accounts for the recurrence relation above.
While these experiments allowed me to guess the correct probability, I wasn't able to prove anything, because the polynomials themselves get  complicated very fast.
$$\begin{align}
p_2(q)&=\frac{q \left(q - 1\right)}{2}\\
p_3(q)&=\frac{q^{3}}{3} - \frac{q}{3}\\
p_4(q)&=\frac{q \left(q - 1\right) \left(3 q^{2} + q + 2\right)}{8}\\
p_5(q)&=\frac{q \left(q - 1\right) \left(q + 1\right) \left(11 q^{2} - 5 q + 6\right)}{30}\\
p_6(q)&=\frac{q \left(q - 1\right) \left(53 q^{4} + 26 q^{3} + 19 q^{2} - 2 q + 24\right)}{144}\\
p_7(q)&=\frac{q \left(q - 1\right) \left(q + 1\right) \left(309 q^{4} - 154 q^{3} + 239 q^{2} - 154 q + 120\right)}{840}\\
&\vdots
\end{align}$$ 
Jyrki Lahtonen has given an elegant solution to the original problem, which incidentally establishes this identity when $q$ is a prime power, but in my experiments, I noticed that it seems likely to be true when $q$ is any positive integer.  Using sympy, I calculated the polynomials $p_n$ for $n\leq25,$ and verified the identity for $q$ in the same range.
I don't have any good ideas about how to prove this.  Since we know it's true for prime powers, I thought about trying to prove that if it's true for relatively prime integers $q$ and $r,$ then it's true for $qr,$ but the problem is that we have to deal with $p_n$ when $n$ is small, and 1) the induction hypothesis doesn't cover that, and 2) the polynomials themselves don't have a convenient explicit formula. I'm not clever enough to find the explicit formula for the $p_n$ given in Felix Matin's answer.  
So the only promising approach I can think of is to find something that the $p_n$ count, even when $q$ is not a prime power, but I have no idea what that would be. 
Of course, the definition of the $p_n$ is valid if $q$ is a real (or even a complex) number.  Can anything be said in these larger domains?
 A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\left.\vphantom{\LARGE A} p_{n}\pars{q}
\,\right\vert_{{\large n\ \geq\ 2} \atop
{\large q\ \in\ \mathbb{N_{\ \geq\ 1}}}} =
q^{n} - \sum_{k = 1}^{n}{k + q - 1 \choose k}
p_{n - k}\pars{q}\,,\
\left\{\begin{array}{rcl}
\ds{p_{0}\pars{q}} & \ds{\equiv} & \ds{1}
\\
\ds{p_{1}\pars{q}} & \ds{\equiv} & \ds{0}
\end{array}\right.}$

$$
\bbx{\mbox{Lets}\ \mc{P}\pars{q,z} \equiv
\sum_{n = 0}^{\infty}p_{n}\pars{q}z^{n} \implies
p_{n}\pars{q} = \bracks{z^{n}}\mc{P}\pars{q,z}}
$$

The above general recurrence is conveniently rewritten as $\pars{~\mbox{with}\ n \geq 2~}$:
$$
p_{n}\pars{q} + qp_{n - 1}\pars{q} =
q^{n} - \sum_{k = 2}^{n}{k + q - 1 \choose k}
p_{n - k}\pars{q}
$$

Then,
\begin{align}
&\sum_{n = 2}^{\infty}p_{n}\pars{q}z^{n} +
q\sum_{n = 2}^{\infty}p_{n - 1}\pars{q}z^{n}
\\ = &\
\sum_{n = 2}^{\infty}q^{n}z^{n} - \
\sum_{n = 2}^{\infty}z^{n}
\sum_{k = 2}^{n}{k + q - 1 \choose k}
p_{n - k}\pars{q}
\\[5mm] &\
\overbrace{\sum_{n = 0}^{\infty}p_{n}\pars{q}z^{n}}
^{\ds{\mc{P}\pars{q,z}}}\ -\
\overbrace{p_{0}\pars{q}}^{\ds{1}}\ -\
\overbrace{p_{1}\pars{q}}^{\ds{0}}\ z\ +\
q\
\overbrace{\sum_{n = 1}^{\infty}p_{n}\pars{q}z^{n + 1}}
^{\ds{z\bracks{\mc{P}\pars{q,z} - 1}}}
\\ = &\
{q^{2}z^{2} \over 1 - qz} -
\sum_{k = 2}^{\infty}\
\underbrace{k + q - 1 \choose k}
_{\ds{{-q \choose k}\pars{-1}^{k}}}\
\underbrace{\sum_{n = k}^{\infty}
p_{n - k}\pars{q}z^{n}}_{\ds{z^{k}\mc{P}\pars{q,z}}}
\\[5mm] &
\bracks{1 + qz +
\sum_{k = 2}^{\infty}{-q \choose k}\pars{-z}^{k}}
\mc{P}\pars{q,z} =
1 + qz + {q^{2}z^{2} \over 1 - qz} = {1 \over 1 - qz}
\\[5mm] &
\bracks{1 + qz +
\pars{1 - z}^{-q} - 1 - qz}\mc{P}\pars{q,z} =
{1 \over 1 - qz}
\\[5mm] &
\implies
\bbx{\mc{P}\pars{q,z} =
{\pars{1 - z}^{q} \over 1 - qz}}
\end{align}

\begin{align}
\mc{P}\pars{q,z} & =
{\pars{1 - z}^{q} \over 1 - qz} =
\bracks{\sum_{i = 0}^{\infty}{q \choose i}\pars{-z}^{i}}
\bracks{\sum_{j = 0}^{\infty}\pars{qz}^{j}}
\\[5mm] & =
\sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty}{q \choose i}
q^{j}\pars{-1}^{i}\sum_{n = 0}^{\infty}z^{n}
\bracks{i + j = n}
\\[5mm] & =
\sum_{n = 0}^{\infty}\braces{\sum_{i = 0}^{\infty}\sum_{j = 0}^{\infty}{q \choose i}
q^{j}\pars{-1}^{i}\bracks{j = n - i}}z^{n}
\\[5mm] & =
\sum_{n = 0}^{\infty}\braces{\sum_{i = 0}^{\infty}{q \choose i}
q^{n - i}\pars{-1}^{i}\bracks{n - i \geq 0}}z^{n}
\\[5mm] & =
\sum_{n = 0}^{\infty}\braces{q^{n}
\sum_{i = 0}^{n}{q \choose i}
\pars{-\,{1 \over q}}^{i}}z^{n}
\end{align}
$$
\bbox[15px,#ffd,border:1px groove navy]{p_{n}\pars{q} = q^{n}\sum_{i = 0}^{n}{q \choose i}
\pars{-\,{1 \over q}}^{i}\,,\qquad
q \in \mathbb{N}_{\ \geq\ 1}}
$$

When $\ds{n \geq q\,,\quad p_{n}\pars{q} =
q^{n}\bracks{1 + \pars{-\,{1 \over q}}}^{q} =
q^{n - q}\pars{q - 1}^{q}}$

