I am reading a paper that defines $P_k(s|t)$ as a polynomial of degree $k$ in $s$ given $t$. Does this mean that each term is of the form $f_{k}(t)s^{k}$? (What does "given $t$" mean?)
The paper says that by equating coefficients in the equation $$P_k(s+u|t+u)=P_k(s|t)+P_k(s|u)$$ then $P_k(s|t)$ must be a polynomial in $s$ and $t$ of degree $\leq k+1$ i.e. $P_k(s|t)=P_{k+1}(s,t)$. Why is $P_k(s|t)$ a polynomial $t$?
Since $P_k(s|t)$ is a polynomial in $s$ for a given $t$, $$ P_k(s|t)=\sum_{i=1}^k f_i(t)s^i $$ If $$ P_k(s+u|t+u)=P_k(s|t) +P_k(s|u) $$ Then $$ \sum_{i=1}^k f_i(t+u)\sum_{j=0}^i \binom{i}{j} s^ju^{i-j}=\sum_{i=1}^k f_i(t)s^i +\sum_{i=1}^k f_i(u)s^i $$ Equating the coefficient on $s^k$ we get $$ f_k(t+u)= f_k(t) + f_k(u) $$ Hence $f_k$ is linear and the first term is a polynomial in $s$ and $t$ of degree $\leq k+1$. Equating the coefficients on $s^{k-1}$ we get $$ kf_k(t+u)u + f_{k-1}(t+u) = f_{k-1}(t)+ f_{k-1}(u) $$ so $f_{k-1}$ must be quadratic in which case the second term is of degree $\leq k+1$. Proceeding recursively, $P_k(s|t)$ is a polynomial in $s$ and $t$ of degree $\leq k+1$.