Prove that S(n,m) is an integer. Let $\mathcal{P}_n(\mathbb{Q})$ be the polynomials of degree at most $n$ with rational coefficients. Let $\gamma=\left((x)_0, \ldots,(x)_n\right)$ be the list of polynomials defined inductively by $(x)_0=1$ and $(x)_{n+1}=(x)_n(x-n)$.

*

*Prove that $\gamma$ is a basis for $\mathcal{P}_n(\mathbb{Q})$ as a vector space over $\mathbb{Q}$.


*Define numbers $s(n, m)$ and $S(n, m)$ by the formulae
$$
  \begin{gathered}
  (x)_n=\sum_{m=1}^n s(n, m) x^m \\
  x^n=\sum_{m=1}^n S(n, m)(x)_m
  \end{gathered}
  $$
Prove that $s(n, m)$ and $S(n, m)$ are integers.


*Prove that $p \in \mathcal{P}_n(\mathbb{Q})$ takes integer values on the integers if and only if it has integer coefficients relative to the basis $\left(\frac{(x)_k}{k !}\right)_{k=0}^n$.
I'm struggling to prove that S(n, m) must be an integer. Clearly gamma is a basis because we have a polynomial of every degree and htey are of different degrees. s(n, m) is an integer because it's the coefficient of a term of the polynomial which are all integers because $n$ is an integer. I tried to prove S(n,m) is an integer and this is what I got
Now we turn our attention to the second function. We have
\begin{equation*}
  \begin{split}
    (x)_n&=\sum_{m=1}^n s(n, m) x^m \\
    (x)_n - s(n,n)x^n &= \sum_{m=1}^{n-1} s(n, m) x^m\\
    x^n &= \frac{1}{s(n,n)}[(x)_n - \sum_{m=1}^{n-1} s(n, m) x^m]
  \end{split}
\end{equation*}
Setting this equal to (2) we have
\begin{equation*}
  \begin{split}
    \frac{1}{s(n,n)}[(x)_n - \sum_{m=1}^{n-1} s(n, m) x^m] &= \sum_{m=1}^n S(n, m)(x)_m\\
    (x)_n - \sum_{m=1}^{n-1} s(n, m) x^m &= s(n,n)\sum_{m=1}^n S(n, m)(x)_m\\
    (x)_n &= s(n,n)\sum_{m=1}^n S(n, m)(x)_m + \sum_{m=1}^{n-1} s(n, m) x^m\\
    (x)_n - s(n, n)S(n, n)(x)_n &= \sum_{m=1}^{n-1} S(n, m)(x)_m + \sum_{m=1}^{n-1} s(n, m) x^m\\
    (x)_n(1 - s(n,n)S(n, n)) &= \sum_{m=1}^{n-1}S(n, m)(x)_m + s(n, m) x^m\\
    (x)_n &= \frac{1}{1 - s(n,n)S(n, n)}\sum_{m=1}^{n-1}S(n, m)(x)_m + s(n, m) x^m\\
  \end{split}
\end{equation*}
Therefore every coefficient of $(x)_n$ is a multiple of $\frac{1}{1 - s(n,n)S(n, n)}$.
This seems a little excessive, but I'm not sure where to go from here. Any help is greatly appreciated :)
 A: I'm just going to press on, assuming that the sums begin at $m = 0$, as per my comment. I'm also going to assume we are working in $\mathcal{P}_k(\Bbb{Q})$, not $\mathcal{P}_n(\Bbb{Q})$, because you use $n$ as a dummy variable later on.
The "high level" version of this is as follows. As you pointed out, $(x)_m$ for $m = 0, \ldots, k$ is a basis for $\mathcal{P}_k(\Bbb{Q})$, due to the degree increasing for each $(x)_m$, making them linearly independent, and there being $k + 1$ of them, matching the degree of $\mathcal{P}_k(\Bbb{Q})$.
The $s(n, m)$ and $S(n, m)$ scalars (without assuming they are integers) form the entries in the change-of-basis matrix between these bases: $B = (1, x, \ldots, x^k)$ and $C = ((x)_0, (x)_1, \ldots, (x)_k)$. In particular, the change-of-basis matrix $P$ from basis $C$ to basis $B$ will be
$$P = \begin{pmatrix}
s(0, 0) & s(1, 0) & s(2, 0) & \cdots & s(k-1,0) & s(k,0) \\
0 & s(1, 1) & s(2, 1) & \cdots & s(k-1,1) & s(k,1) \\
0 & 0 & s(2, 2) & \cdots & s(k-1,2) & s(k,2) \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \cdots & s(k-1, k-1) & s(k,k-1) \\
0 & 0 & 0 & \cdots & 0 & s(k,k)
\end{pmatrix}.$$
Now, as you know, the $s(m, n)$s are integers. Also, it's not difficult to see that $s(n, n) = 1$ for all $n$ (since $(x)_n$ is a monic polynomial of degree $n$). Note that $P$ is upper-triangular with determinant $1$. This means that $P$ element of $SL_k(\Bbb{Z})$, the set of integer matrices with determinant $1$, which is a group under matrix multiplication. In particular, it means that $P^{-1} \in SL_k(\Bbb{Z})$, i.e. the change-of-basis matrix $P^{-1}$ from $B$ to $C$, which consists of $0$s and the $S(m, n)$ terms, also consists of integers and has a determinant of $1$. This proves the result.
The key result here can be seen from the inverse formula using the adjugate matrix $\operatorname{Adj}(P)$ of $P$, a matrix whose entries are just determinants of minors of $P$, all of which are polynomial functions of the entries of $P$, and hence must be integers. The adjugate satisfies $\operatorname{Adj}(P)P = P\operatorname{Adj}(P) = \det(P)I$, which can be proven using the cofactor expansions of the determinant. Since $\operatorname{det}P = 1$, this adjugate is the inverse, and consists of integer entries.

Or, we could take a more elementary approach, and use induction on $n$. Clearly
$$x^0 = 1(x)_0 + 0(x)_1 + \ldots + 0(x)_k,$$
which proves the $n = 0$ case.
Suppose $n$ is such that
$$x^n = S(n, 0) (x)_0 + S(n, 1) (x)_1 + \ldots + S(n, k) (x)_k,$$
where $S(n, 0), S(n, 1), \ldots, S(n, k)$ are integers. Then,
$$x^{n+1} = S(n, 0) x(x)_0 + S(n, 1) x(x)_1 + \ldots + S(n, k) x(x)_k.$$
Note that $x(x)_i = (x - i)(x)_i + i(x)_i = (x)_{i+1} + i(x)_i$, hence
\begin{align*}
x^{n+1} &= S(n, 0) ((x)_1 + 0(x)_0) + S(n, 1) ((x)_2 + 1(x)_1) + \ldots + S(n, k) ((x)_{k+1}+k(x)_k) \\
&= 0(x)_0 + (S(n, 0) + 1S(n, 1))(x)_1 + (S(n, 1) + 2S(n, 2))(x)_2 + \ldots \\
&+ (S(n, k-1) + kS(n, k))(x)_k + S(n, k)(x)_{k+1}.
\end{align*}
Note: the coefficients are all integers, because $S(n, m)$ were all integers, for $m = 0, \ldots, k$. Thus, the result is proven by induction.
