"Binomial coefficients" generalized via polynomial iteration

Question

This is a question I will answer myself immediately by repeating one of my old AoPS posts, since the latter post no longer renders on AoPS.

Convention. In the following, whenever $A$ is a commutative ring with $1$, and $f$ and $g$ are two polynomials over $A$ in the variable $x$, then we denote by $f\left[g\right]$ the evaluation of the polynomial $f$ at $g$. This evaluation is defined as the image of $f$ under the $A$-algebra homomorphism $A\left[x\right] \to A\left[x\right]$ which maps $x$ to $g$ (this homomorphism is unique, due to the universal property of the polynomial ring). Equivalently, this evaluation is $\sum_{i\geq 0} f_i g^i$, where $f_0, f_1, f_2, \ldots$ are the coefficients of the polynomial $f$ before $x^0, x^1, x^2, \ldots$, respectively.

Note that the evaluation $f\left[g\right]$ is frequently denoted by $f\left(g\right)$ in literature, but this $f\left(g\right)$ notation is slightly ambiguous, because $f\left(g\right)$ can also mean the product of the polynomials $f$ and $g$ (in particular, this often happens when $g$ is a complicated sum, so that the parentheses around $g$ are required), and this is an entirely different thing. Thus we are always going to denote the evaluation by $f\left[g\right]$, and never by $f\left(g\right)$.

Also note that every polynomial $f\in A\left[x\right]$ satisfies $f\left[x\right]=f$ and $x\left[f\right]=f$.

Also, I let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$.

Theorem 1. Let $A$ be a commutative ring with $1$, and let $f\in A\left[x\right]$ be a polynomial over $A$ in the variable $x$. Let us define a polynomial $f_n\in A\left[x\right]$ for every $n\in\mathbb{N}$. Namely, we define $f_n$ by induction over $n$: We start with $f_0=x$, and continue with the recursive equation $f_{n+1}=f\left[f_n\right]$ for every $n\in\mathbb N$. [Note that I hesitate to denote $f_n$ by $f^n$ since $f^n$ already stands for "$n$-th power of $f$ with respect to multiplication of polynomials", and that's something different from $f_n$.] Then, for any nonnegative integers $n$ and $k$, we have \begin{equation} \prod_{i=1}^n\left(f_i-x\right) \mid \prod_{i=k+1}^{k+n}\left(f_i-x\right) \end{equation} in the ring $A\left[x\right]$.

Theorem 2. Let $A$, $f$ and $f_n$ be as in Theorem 1. Then, for any two coprime positive integers $m$ and $n$, we have \begin{equation} \left(f_m - x\right) \left(f_n - x\right) \mid \left(f_{mn} - x\right) \left(f - x\right) \end{equation} in the ring $A\left[x\right]$.

The question is to prove these two theorems.

Theorem 1 has been posted by gammaduc at https://artofproblemsolving.com/community/c7h412796 ; Theorem 2 has been posted by gammaduc at https://artofproblemsolving.com/community/c7h412797 .

Answer 1

Proof of Theorem 1

[Remark: The following proof was written in 2011 and only mildly edited now. There are things in it that I would have done better if I were to rewrite it.]

Proof of Theorem 1. First, let us prove something seemingly obvious: Namely, we will prove that for any nonnegative integers $a$ and $b$ such that $a\geq b$, we have

\begin{equation} f_b\left[f_{a-b}\right] = f_a . \label{darij-proof.1} \tag{1} \end{equation}

This fact appears trivial if you think of polynomials as functions (in which case $f_k$ is really just $\underbrace{f \circ f \circ \cdots \circ f}_{k \text{ times}}$); the only problem with this approach is that polynomials are not functions. Thus, let me give a proof of \eqref{darij-proof.1}:

[Proof of \eqref{darij-proof.1}. For every polynomial $g\in A\left[x\right]$, let $R_g$ be the map $A\left[x\right]\to A\left[x\right]$ mapping every $p\in A\left[x\right]$ to $g\left[p\right]$. Note that this map $R_g$ is not a ring homomorphism (in general), but a polynomial map.

Next we notice that $f_n = R_f^n\left(x\right)$ for every $n\in\mathbb N$. In fact, this can be proven by induction over $n$: The induction base (the case $n=0$) is trivial (since $f_0=x$ and $R_f^0\left(x\right)=\operatorname{id}\left(x\right)=x$). For the induction step, assume that some $m\in\mathbb N$ satisfies $f_m = R_f^m\left(x\right)$. Then, $m+1$ satisfies

\begin{align} f_{m+1} &= f\left[f_m\right] \qquad \left(\text{by the recursive definition of $f_{m+1}$}\right) \\ &= R_f\left(f_m\right) \qquad \left(\text{since $R_f\left(f_m\right)=f\left[f_m\right]$ by the definition of $R_f$}\right) \\ &= R_f\left(R_f^m\left(x\right)\right) \qquad \left(\text{since $f_m=R_f^m\left(x\right)$}\right) \\ &= R_f^{m+1}\left(x\right) . \end{align}

This completes the induction.

We thus have shown that $f_n = R_f^n\left(x\right)$ for every $n\in\mathbb N$. Since $f_n=f_n\left[x\right]=R_{f_n}\left(x\right)$ (because the definition of $R_{f_n}$ yields $R_{f_n}\left(x\right)=f_n\left[x\right]$), this rewrites as follows:

\begin{equation} R_{f_n}\left(x\right) = R_f^n\left(x\right) \qquad \text{ for every $n\in\mathbb N$.} \label{darij-proof.1.5} \tag{2} \end{equation}

Now we will prove that

\begin{equation} f_n\left[p\right] = R_f^n\left(p\right) \text{ for every } n\in\mathbb N \text{ and every } p\in A\left[x\right] . \label{darij-proof.2} \tag{3} \end{equation}

[Proof of \eqref{darij-proof.2}. Let $p\in A\left[x\right]$ be any polynomial. By the universal property of the polynomial ring $A\left[x\right]$, there exists an $A$-algebra homomorphism $\Phi : A\left[x\right] \to A\left[x\right]$ such that $\Phi\left(x\right) = p$. Consider this $\Phi$. Then, for every polynomial $q\in A\left[x\right]$, we have $\Phi\left(q\right) = q\left[p\right]$. (This is the reason why $\Phi$ is commonly called the evaluation homomorphism at $p$.)

Now, every $A$-algebra homomorphism $A\left[x\right] \to A\left[x\right]$ commutes with $R_g$ for every $g\in A\left[x\right]$ (this is just a formal way to state the known fact that every $A$-algebra homomorphism commutes with every polynomial map). Applying this to the homomorphism $\Phi$, we conclude that $\Phi$ commutes with $R_g$ for every $g\in A\left[x\right]$. Thus, in particular, $\Phi$ commutes with $R_{f_n}$ and with $R_f$. Since $\Phi$ commutes with $R_f$, it is clear that $\Phi$ also commutes with $R_f^n$, and thus $\Phi\left(R_f^n\left(x\right)\right)=R_f^n\left(\Phi\left(x\right)\right)$. Since $\Phi\left(x\right)=p$, this rewrites as $\Phi\left(R_f^n\left(x\right)\right)=R_f^n\left(p\right)$. On the other hand, $\Phi$ commutes with $R_{f_n}$, so that $\Phi\left(R_{f_n}\left(x\right)\right)=R_{f_n}\left(\underbrace{\Phi\left(x\right)}_{=p}\right)=R_{f_n}\left(p\right)=f_n\left[p\right]$ (by the definition of $R_{f_n}$). In view of \eqref{darij-proof.1.5}, this rewrites as $\Phi\left(R_f^n\left(x\right)\right) = f_n\left[p\right]$. Hence,

\begin{equation} f_n\left[p\right] = \Phi\left(R_f^n\left(x\right)\right) = R_f^n\left(p\right) , \end{equation}

and thus \eqref{darij-proof.2} is proven.]

Now, we return to the proof of \eqref{darij-proof.1}: Applying \eqref{darij-proof.2} to $n=b$ and $p=f_{a-b}$, we obtain $f_b\left[f_{a-b}\right] = R_f^b\left(f_{a-b}\right)$. Since $f_{a-b} = f_{a-b}\left[x\right] = R_f^{a-b}\left(x\right)$ (by \eqref{darij-proof.2}, applied to $n=a-b$ and $p=x$), this rewrites as

\begin{equation} f_b\left[f_{a-b}\right] = R_f^b\left(R_f^{a-b}\left(x\right)\right) = \underbrace{\left(R_f^b\circ R_f^{a-b}\right)}_{=R_f^{b+\left(a-b\right)}=R_f^a} \left(x\right) = R_f^a\left(x\right) . \end{equation}

Compared with $f_a = f_a\left[x\right] = R_f^a\left(x\right)$ (by \eqref{darij-proof.2}, applied to $n=a$ and $p=x$), this yields $f_b\left[f_{a-b}\right] = f_a$. Thus, \eqref{darij-proof.1} is proven.]

Now here is something less obvious:

For any nonnegative integers $a$ and $b$ such that $a\geq b$, we have

\begin{equation} f_{a-b}-x\mid f_a-f_b \qquad \text{ in } A\left[x\right] . \label{darij-proof.3} \tag{4} \end{equation}

[Proof of \eqref{darij-proof.3}. Let $a$ and $b$ be nonnegative integers such that $a\geq b$. Let $I$ be the ideal of $A\left[x\right]$ generated by the polynomial $f_{a-b}-x$. Then, $f_{a-b}-x\in I$, so that $f_{a-b}\equiv x\mod I$.

We recall a known fact: If $B$ is a commutative $A$-algebra, if $J$ is an ideal of $B$, if $p$ and $q$ are two elements of $B$ satisfying $p\equiv q\mod J$, and if $g\in A\left[x\right]$ is a polynomial, then $g\left[p\right]\equiv g\left[q\right]\mod J$. (This fact is proven by seeing that $p^u\equiv q^u\mod J$ for every $u\in\mathbb N$.) Applying this fact to $B=A\left[x\right]$, $J=I$, $p=f_{a-b}$, $q=x$ and $g=f_b$, we obtain $f_b\left[f_{a-b}\right] \equiv f_b\left[x\right] = f_b \mod I$. Due to \eqref{darij-proof.1}, this becomes $f_a \equiv f_b \mod I$. Thus, $f_a-f_b \in I$. Since $I$ is the ideal of $A\left[x\right]$ generated by $f_{a-b}-x$, this yields that $f_{a-b}-x\mid f_a-f_b$. This proves \eqref{darij-proof.3}.]

For any nonnegative integers $a$ and $b$ such that $a\geq b$, let $f_{a\mid b}$ be some polynomial $h\in A\left[x\right]$ such that $f_a-f_b = h\cdot\left(f_{a-b}-x\right)$. Such a polynomial $h$ exists according to \eqref{darij-proof.3}, but needs not be unique (e. g., if $f=x$ or $a=b$, it can be arbitrary), so we may have to take choices here. Thus,

\begin{equation} f_a-f_b = f_{a\mid b} \cdot\left(f_{a-b}-x\right) \label{darij-proof.4} \tag{5} \end{equation} for any nonnegative integers $a$ and $b$ such that $a\geq b$.

Let us now define a polynomial $f_{a,b} \in A\left[x\right]$ for any nonnegative integers $a$ and $b$. Namely, we define this polynomial by induction over $a$:

Induction base: For $a=0$, let $f_{a,b}$ be $\delta_{0,b}$ (where $\delta$ means Kronecker's delta, defined by $\delta_{u,v}= \begin{cases} 1, & \text{if }u=v;\\ 0, & \text{if }u\neq v\end{cases}$ for any two objects $u$ and $v$).

Induction step: Let $r\in\mathbb N$ be positive. If $f_{r-1,b}$ is defined for all $b \in \mathbb N$, then let us define $f_{r,b}$ for all $b \in \mathbb N$ as follows:

\begin{align} f_{r,b} &= f_{r-1,b} + f_{r\mid r-b} f_{r-1,b-1} \text{ if } 0 \leq b \leq r \text{ (where $f_{r-1,-1}$ means $0$)}; \\ f_{r,b} &= 0 \text{ if } b > r . \end{align}

This way, we inductively have defined $f_{a,b}$ for all nonnegative integers $a$ and $b$.

We now claim that

\begin{equation} f_{a,b} \prod_{i=1}^b\left(f_i-x\right) = \prod_{i=a-b+1}^{a}\left(f_i-x\right) \label{darij-proof.5} \tag{6} \end{equation}

for any nonnegative integers $a$ and $b$ such that $a\geq b$.

[Proof of \eqref{darij-proof.5}. We will prove \eqref{darij-proof.5} by induction over $a$:

Induction base: For $a=0$, proving \eqref{darij-proof.5} is very easy (notice that $0=a\geq b$ entails $b=0$, and use $f_{0,0} = 1$). Thus, we can consider the induction base as completed.

Induction step: Let $r\in\mathbb N$ be positive. Assume that \eqref{darij-proof.5} holds for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r-1$. Now let us prove \eqref{darij-proof.5} for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r$:

Let $a$ and $b$ be nonnegative integers such that $a\geq b$ and $a=r$.

Then, $r=a\geq b$. Thus, $b$ is a nonnegative integer satisfying $b\leq r$. This shows that we must be in one of the following three cases:

Case 1: We have $b=0$.

Case 2: We have $1\leq b\leq r-1$.

Case 3: We have $b=r$.

Let us first consider Case 1: In this case, $b=0$. The recursive definition of $f_{r,b}$ yields

\begin{equation} f_{r,0} = f_{r-1,0} + f_{r\mid r-0} \underbrace{f_{r-1, 0-1}}_{=f_{r-1,-1} = 0} = f_{r-1,0} . \end{equation}

We can apply \eqref{darij-proof.5} to $r-1$ and $0$ instead of $a$ and $b$ (since we assumed that \eqref{darij-proof.5} holds for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r-1$). This yields the identity

\begin{equation} f_{r-1,0} \prod_{i=1}^0\left(f_i-x\right) = \prod_{i=r-1-0+1}^{r-1}\left(f_i-x\right) . \end{equation}

Since both products $\prod_{i=1}^0\left(f_i-x\right)$ and $\prod_{i=r-1-0+1}^{r-1}\left(f_i-x\right)$ are equal to $1$ (since they are empty products), this simplifies to $f_{r-1,0} \cdot 1 = 1$, so that $f_{r-1,0} = 1$. Now,

\begin{equation} f_{r,0} \underbrace{\prod_{i=1}^0\left(f_i-x\right)}_{=\left(\text{empty product}\right)=1} = f_{r,0} = f_{r-1,0} = 1 \end{equation}

and

\begin{equation} \prod_{i=r-0+1}^{r}\left(f_i-x\right) = \left(\text{empty product}\right) = 1 . \end{equation}

Comparing these equalities yields

\begin{equation} f_{r,0} \prod_{i=1}^0\left(f_i-x\right) = \prod_{i=r-0+1}^{r}\left(f_i-x\right) . \end{equation}

Since $0=b$ and $r=a$, this rewrites as

\begin{equation} f_{a,b} \prod_{i=1}^b\left(f_i-x\right) = \prod_{i=a-b+1}^{a}\left(f_i-x\right) . \end{equation}

In other words, we have proven \eqref{darij-proof.5} for our $a$ and $b$ in Case 1.

Next let us consider Case 2: In this case, $1\leq b\leq r-1$. Hence, $0 \leq b-1 \leq r-1$ and $r-1 \geq b \geq b-1$.

In particular, $r-1$ and $b-1$ are nonnegative integers satisfying $r-1 \geq b-1$. Hence, we can apply \eqref{darij-proof.5} to $r-1$ and $b-1$ instead of $a$ and $b$ (since we assumed that \eqref{darij-proof.5} holds for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r-1$). This yields the identity

\begin{equation} f_{r-1,b-1} \prod_{i=1}^{b-1}\left(f_i-x\right) = \prod_{i=\left(r-1\right)-\left(b-1\right)+1}^{r-1}\left(f_i-x\right) . \end{equation}

Since $\left(r-1\right)-\left(b-1\right)+1=r-b+1$, this simplifies to

\begin{equation} f_{r-1,b-1} \prod_{i=1}^{b-1}\left(f_i-x\right) = \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) . \end{equation}

On the other hand, $r-1$ and $b-1$ are nonnegative integers satisfying $r-1 \geq b$. Thus, we can apply \eqref{darij-proof.5} to $r-1$ and $b$ instead of $a$ and $b$ (since we assumed that \eqref{darij-proof.5} holds for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r-1$). This gives us

\begin{equation} f_{r-1,b} \prod_{i=1}^{b}\left(f_i-x\right) = \prod_{i=\left(r-1\right)-b+1}^{r-1}\left(f_i-x\right) . \end{equation}

Since $\left(r-1\right)-b+1=r-b$, this rewrites as

\begin{equation} f_{r-1,b} \prod_{i=1}^{b}\left(f_i-x\right) = \prod_{i=r-b}^{r-1}\left(f_i-x\right) = \left(f_{r-b}-x\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) \end{equation}

(because $r-1 \geq r-b$).

Since $0\leq b\leq r$, we have $0\leq r-b\leq r$, and \eqref{darij-proof.4} (applied to $r$ and $r-b$ instead of $a$ and $b$) yields

\begin{equation} f_r-f_{r-b} = f_{r\mid r-b}\cdot \left(f_{r-\left(r-b\right)}-x\right) . \end{equation}

Since $r-\left(r-b\right)=b$, this simplifies to

\begin{equation} f_r-f_{r-b} = f_{r\mid r-b}\cdot \left(f_b-x\right) . \label{darij-proof.5.5} \tag{7} \end{equation}

Since $0\leq b\leq r$, the recursive definition of $f_{r,b}$ yields

\begin{equation} f_{r,b} = f_{r-1,b} + f_{r\mid r-b} f_{r-1,b-1} . \end{equation}

Thus,

\begin{align} & f_{r,b} \prod_{i=1}^b\left(f_i-x\right) \\ &= \left(f_{r-1,b} + f_{r\mid r-b} f_{r-1,b-1}\right) \prod_{i=1}^b\left(f_i-x\right) \\ &= f_{r-1,b} \prod_{i=1}^b\left(f_i-x\right) + f_{r\mid r-b} f_{r-1,b-1} \underbrace{\prod_{i=1}^b\left(f_i-x\right)}_{=\left(f_b-x\right)\prod_{i=1}^{b-1}\left(f_i-x\right)} \\ & = f_{r-1,b} \prod_{i=1}^b\left(f_i-x\right) + f_{r\mid r-b} f_{r-1,b-1} \left(f_b-x\right) \prod_{i=1}^{b-1}\left(f_i-x\right) \\ & = \underbrace{f_{r-1,b} \prod_{i=1}^b\left(f_i-x\right)}_{= \left(f_{r-b}-x\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) } + \underbrace{f_{r\mid r-b} \cdot \left(f_b-x\right)}_{\substack{=f_r-f_{r-b} \\ \text{(by \eqref{darij-proof.5.5})}}} \underbrace{f_{r-1,b-1} \prod_{i=1}^{b-1}\left(f_i-x\right)}_{= \prod_{i=r-b+1}^{r-1}\left(f_i-x\right)} \\ &= \left(f_{r-b}-x\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) + \left(f_r-f_{r-b}\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) \\ &= \underbrace{\left( \left(f_{r-b}-x\right) + \left(f_r-f_{r-b}\right) \right)}_{=f_r-x} \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) \\ &= \left(f_r-x\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) = \prod_{i=r-b+1}^{r}\left(f_i-x\right) . \end{align}

Since $r=a$, this rewrites as

\begin{equation} f_{a,b} \prod_{i=1}^b\left(f_i-x\right) = \prod_{i=a-b+1}^{a}\left(f_i-x\right) . \end{equation}

In other words, we have proven \eqref{darij-proof.5} for our $a$ and $b$ in Case 2.

Next let us consider Case 3: In this case, $b=r$.

In this case, we proceed exactly as in Case 2, except for one small piece of the argument: Namely, in Case 2 we were allowed to apply \eqref{darij-proof.5} to $r-1$ and $b$ instead of $a$ and $b$, but now in Case 3 we are not allowed to do this anymore (because \eqref{darij-proof.5} requires $a\geq b$). Therefore, we need a different way to prove the equality

\begin{equation} f_{r-1,b} \prod_{i=1}^{b}\left(f_i-x\right) = \left(f_{r-b}-x\right) \prod_{i=r-b+1}^{r-1}\left(f_i-x\right) \label{darij-proof.6} \tag{8} \end{equation}

in Case 3. Here is such a way:

By the inductive definition of $f_{r-1,b}$, we have $f_{r-1,b}=0$ (since $b=r>r-1$). Thus, the left hand side of \eqref{darij-proof.6} equals $0$. On the other hand, $b=r$ yields $f_{r-b}=f_{r-r}=f_0=x$, so that $f_{r-b}-x=0$. Thus, the right hand side of \eqref{darij-proof.6} equals $0$. Since both the left hand side and the right hand side of \eqref{darij-proof.6} equal $0$, it is now clear that the equality \eqref{darij-proof.6} is true, and thus we can proceed as in Case 2. Hence, \eqref{darij-proof.5} is proven for our $a$ and $b$ in Case 3.

We have thus proven that \eqref{darij-proof.5} holds for our $a$ and $b$ in each of the three possible cases 1, 2 and 3. Thus, \eqref{darij-proof.5} is proven for any nonnegative integers $a$ and $b$ such that $a\geq b$ and $a=r$. This completes the induction step.

Thus, the induction proof of \eqref{darij-proof.5} is done.]

Now, any nonnegative integers $n$ and $k$ satisfy

\begin{equation} f_{k+n,n} \prod_{i=1}^n\left(f_i-x\right) = \prod_{i=\left(k+n\right)-n+1}^{k+n}\left(f_i-x\right) \end{equation}

(by \eqref{darij-proof.5}, applied to $a=k+n$ and $b=n$). Since $\left(k+n\right)-n=k$, this simplifies to

\begin{equation} f_{k+n,n} \prod_{i=1}^n\left(f_i-x\right) = \prod_{i=k+1}^{k+n}\left(f_i-x\right) . \end{equation}

This immediately yields Theorem 1. $\blacksquare$

Answer 2

Proof of Theorem 2

The proof of Theorem 2 I shall give below is merely a generalization of GreenKeeper's proof at AoPS, with all uses of specific properties of $A$ excised.

If $a_1, a_2, \ldots, a_m$ are some elements of a commutative ring $R$, then we let $\left< a_1, a_2, \ldots, a_m \right>$ denote the ideal of $R$ generated by $a_1, a_2, \ldots, a_m$. (This is commonly denoted by $\left(a_1, a_2, \ldots, a_m\right)$, but I want a less ambiguous notation.)

Lemma 3. Let $R$ be a commutative ring. Let $a, b, c, u, v, p$ be six elements of $R$ such that $a \mid p$ and $b \mid p$ and $c = au+bv$. Then, $ab \mid cp$.

Proof of Lemma 3. We have $a \mid p$; thus, $p = ad$ for some $d \in R$. Consider this $d$.

We have $b \mid p$; thus, $p = be$ for some $e \in R$. Consider this $e$.

Now, from $c = au+bv$, we obtain $cp = \left(au+bv\right)p = au\underbrace{p}_{=be} + bv\underbrace{p}_{=ad} = aube + bvad = ab\left(ue+vd\right)$. Hence, $ab \mid cp$. This proves Lemma 3. $\blacksquare$

Lemma 4. Let $A$, $f$ and $f_n$ be as in Theorem 1. Then, for any nonnegative integers $a$ and $b$ such that $a \geq b$, we have \begin{equation} f_{a-b}-x\mid f_a-f_b \qquad \text{ in } A\left[x\right] . \end{equation}

Proof of Lemma 4. Lemma 4 is precisely the relation \eqref{darij-proof.3} from the proof of Theorem 1; thus, we have already shown it. $\blacksquare$

Lemma 5. Let $A$, $f$ and $f_n$ be as in Theorem 1. Let $a$ and $b$ be nonnegative integers such that $a \geq b$. Then, $\left< f_a - x, f_b - x \right> = \left< f_{a-b} - x, f_b - x \right>$ as ideals of $A\left[x\right]$.

Proof of Lemma 5. We have $a \geq b$, thus $0 \leq b \leq a$. Hence, $0 \leq a-b \leq a$. Therefore, $a-b$ is a nonnegative integer such that $a \geq a-b$. Hence, Lemma 4 (applied to $a-b$ instead of $b$) yields $f_{a-\left(a-b\right)} - x \mid f_a - f_{a-b}$. In view of $a-\left(a-b\right) = b$, this rewrites as $f_b - x \mid f_a - f_{a-b}$. In other words, $f_a - f_{a-b} \in \left< f_b - x \right>$.

Hence, $f_a - f_{a-b} \in \left< f_b - x \right> \subseteq \left< f_{a-b} - x, f_b - x \right>$. Thus, both elements $f_a - f_{a-b}$ and $f_{a-b} - x$ of $A\left[x\right]$ belong to the ideal $\left< f_{a-b} - x, f_b - x \right>$. Hence, their sum $\left(f_a - f_{a-b}\right) + \left(f_{a-b} - x\right)$ must belong to this ideal as well. In other words, \begin{equation} \left(f_a - f_{a-b}\right) + \left(f_{a-b} - x\right) \in \left< f_{a-b} - x, f_b - x \right> . \end{equation} In view of $\left(f_a - f_{a-b}\right) + \left(f_{a-b} - x\right) = f_a - x$, this rewrites as $f_a - x \in \left< f_{a-b} - x, f_b - x \right>$. Combining this with the obvious fact that $f_b - x \in \left< f_{a-b} - x, f_b - x \right>$, we conclude that both generators of the ideal $\left< f_a - x, f_b - x \right>$ belong to $\left< f_{a-b} - x, f_b - x \right>$. Hence, \begin{equation} \left< f_a - x, f_b - x \right> \subseteq \left< f_{a-b} - x, f_b - x \right> . \label{darij-proof2.1} \tag{11} \end{equation}

On the other hand, $f_a - f_{a-b} \in \left< f_b - x \right> \subseteq \left< f_a - x, f_b - x \right>$. Thus, both elements $f_a - f_{a-b}$ and $f_a - x$ of $A\left[x\right]$ belong to the ideal $\left< f_a - x, f_b - x \right>$. Hence, their difference $\left(f_a - x\right) - \left(f_a - f_{a-b}\right)$ must belong to this ideal as well. In other words, \begin{equation} \left(f_a - x\right) - \left(f_a - f_{a-b}\right) \in \left< f_a - x, f_b - x \right> . \end{equation} In view of $\left(f_a - x\right) - \left(f_a - f_{a-b}\right) = f_{a-b} - x$, this rewrites as $f_{a-b} - x \in \left< f_a - x, f_b - x \right>$. Combining this with the obvious fact that $f_b - x \in \left< f_a - x, f_b - x \right>$, we conclude that both generators of the ideal $\left< f_{a-b} - x, f_b - x \right>$ belong to $\left< f_a - x, f_b - x \right>$. Hence, \begin{equation} \left< f_{a-b} - x, f_b - x \right> \subseteq \left< f_a - x, f_b - x \right> . \end{equation} Combining this with \eqref{darij-proof2.1}, we obtain $\left< f_a - x, f_b - x \right> = \left< f_{a-b} - x, f_b - x \right>$. This proves Lemma 5. $\blacksquare$

Lemma 6. Let $A$, $f$ and $f_n$ be as in Theorem 1. Let $a$ and $b$ be two nonnegative integers. Then, \begin{equation} \left< f_a - x, f_b - x \right> = \left< f_{\gcd\left(a,b\right)} - x \right> \end{equation} as ideals of $A\left[x\right]$.

Here, we follow the convention that $\gcd\left(0,0\right) = 0$. Note that \begin{equation} \gcd\left(a,b\right) = \gcd\left(a-b,b\right) \qquad \text{for all integers $a$ and $b$.} \label{darij.proof2.gcd-inva} \tag{12} \end{equation}

Proof of Lemma 6. We shall prove Lemma 6 by strong induction on $a+b$:

Induction step: Fix a nonnegative integer $N$. Assume (as the induction hypothesis) that Lemma 6 holds whenever $a+b < N$. We must now show that Lemma 6 holds whenever $a+b = N$.

We have assumed that Lemma 6 holds whenever $a+b < N$. In other words, if $a$ and $b$ are two nonnegative integers satisfying $a+b < N$, then \begin{equation} \left< f_a - x, f_b - x \right> = \left< f_{\gcd\left(a,b\right)} - x \right> . \label{darij.proof2.l6.pf.1} \tag{13} \end{equation}

Now, fix two nonnegative integers $a$ and $b$ satisfying $a+b = N$. We want to prove that \begin{equation} \left< f_a - x, f_b - x \right> = \left< f_{\gcd\left(a,b\right)} - x \right> . \label{darij.proof2.l6.pf.2} \tag{14} \end{equation} Since our situation is symmetric in $a$ and $b$, we can WLOG assume that $a \geq b$ (since otherwise, we can just swap $a$ with $b$). Assume this.

We have $f_0 = x$ and thus $f_0 - x = 0$. Hence, \begin{equation} \left< f_a - x, f_0 - x \right> = \left< f_a - x, 0 \right> = \left< f_a - x \right> = \left< f_{\gcd\left(a,0\right)} - x \right> \end{equation} (since $a = \gcd\left(a,0\right)$). Hence, \eqref{darij.proof2.l6.pf.2} holds if $b = 0$. Thus, for the rest of the proof of \eqref{darij.proof2.l6.pf.2}, we WLOG assume that we don't have $b = 0$. Hence, $b > 0$, so that $a+b > a$. Therefore, $\left(a-b\right) + b = a < a+b = N$. Moreover, $a-b$ is a nonnegative integer (since $a \geq b$). Therefore, \eqref{darij.proof2.l6.pf.1} (applied to $a-b$ instead of $a$) yields \begin{equation} \left< f_{a-b} - x, f_b - x \right> = \left< f_{\gcd\left(a-b,b\right)} - x \right> . \end{equation} Comparing this with the equality $\left< f_a - x, f_b - x \right> = \left< f_{a-b} - x, f_b - x \right>$ (which follows from Lemma 5), we obtain \begin{equation} \left< f_a - x, f_b - x \right> = \left< f_{\gcd\left(a-b,b\right)} - x \right> . \end{equation} In view of $\gcd\left(a-b,b\right) = \gcd\left(a,b\right)$ (which follows from \eqref{darij.proof2.gcd-inva}), this rewrites as \begin{equation} \left< f_a - x, f_b - x \right> = \left< f_{\gcd\left(a,b\right)} - x \right> . \end{equation} Thus, \eqref{darij.proof2.l6.pf.2} is proven.

Now, forget that we fixed $a$ and $b$. We thus have shown that if $a$ and $b$ are two nonnegative integers satisfying $a+b = N$, then \eqref{darij.proof2.l6.pf.2} holds. In other words, Lemma 6 holds whenever $a+b = N$. This completes the induction step. Hence, Lemma 6 is proven by induction. $\blacksquare$

Lemma 7. Let $A$, $f$ and $f_n$ be as in Theorem 1. Let $p$ and $q$ be nonnegative integers such that $p \mid q$ (as integers). Then, $f_p - x \mid f_q - x$ in $A\left[x\right]$.

Proof of Lemma 7. We have $\gcd\left(p,q\right) = p$ (since $p \mid q$). Applying Lemma 6 to $a = p$ and $b = q$, we obtain \begin{equation} \left< f_p - x, f_q - x \right> = \left< f_{\gcd\left(p,q\right)} - x \right> = \left< f_p - x \right> \end{equation} (since $\gcd\left(p,q\right) = p$). Hence, \begin{equation} f_q - x \in \left< f_p - x, f_q - x \right> = \left< f_p - x \right> . \end{equation} In other words, $f_p - x \mid f_q - x$. This proves Lemma 7. $\blacksquare$

Proof of Theorem 2. Let $m$ and $n$ be two coprime positive integers. Thus, $\gcd\left(m,n\right) = 1$ (since $m$ and $n$ are coprime). Hence, $f_{\gcd\left(m,n\right)} = f_1 = f$.

Lemma 7 (applied to $p=m$ and $q = mn$) yields $f_m - x \mid f_{mn} - x$ (since $m \mid mn$ as integers). Lemma 7 (applied to $p=n$ and $q = mn$) yields $f_n - x \mid f_{mn} - x$ (since $n \mid mn$ as integers).

But Lemma 6 (applied to $a = m$ and $b = n$) yields \begin{equation} \left< f_m - x, f_n - x \right> = \left< f_{\gcd\left(m,n\right)} - x \right> = \left< f - x \right> \end{equation} (since $f_{\gcd\left(m,n\right)} = f$). Hence, $f - x \in \left< f - x \right> = \left< f_m - x, f_n - x \right>$. In other words, there exist two elements $u$ and $v$ of $A\left[x\right]$ such that $f - x = \left(f_m - x\right) u + \left(f_n - x \right) v$. Consider these $u$ and $v$.

Now, Lemma 3 (applied to $R = A \left[x\right]$, $a = f_m - x$, $b = f_n - x$, $c = f - x$ and $p = f_{mn} - x$) yields $\left(f_m - x\right) \left(f_n - x\right) \mid \left(f - x\right) \left(f_{mn} - x\right) = \left(f_{mn} - x\right) \left(f - x\right)$. This proves Theorem 2. $\blacksquare$

Answer 3

Notation and Lemmas

I will let $$\def\c[#1]{^{\circ #1}}f\c[n]:= f_n$$ Letting $f\circ g=f[g]$, I claim $\circ$ is associative. This follows because any polynomial defines a map $f:A\to A$, and the polynomial corresponding the composition of the maps $f,g:A\to A$ can be shown to be $f\circ g$. This immediately implies that

Lemma 1: $ f\c[(a+b)] = f\c[a][f\c[b]] $

We also have

Lemma 2: For all $n,k\ge 0$, $f\c[k]-x$ divides $f\c[(n+k)]-f\c[n]$

Proof: Writing $f\c[n]=\sum_{h=0}^d a_h x^h$, then $$ f\c[(n+k)]-f\c[n]=f\c[n][f\c[k]] - f\c[n]=\sum_{h=0}^d a_h((f\c[k])^h-x^h) $$ Since $f\c[k]-x$ divides $(f\c[k])^h-x^h$ for all $h\ge 0$, it follows $f\c[k]-x$ divides $f\c[(n+k)]-f\c[n]$.

Lemma 3: $f\c[n]-x$ divides $f\c[mn]-x$

Proof: Apply Lemma 2 to each summand in $$ (f\c[mn]-f\c[(m-1)n])+(f\c[(m-1)n]-f\c[(m-2)n])+\dots+(f\c[n]-x). $$

Theorem 1

First, I deal with the trivial case where $f\c[i]=x$ for some $1\le i \le n$. This implies by induction on $m$ that $f\c[mi]=x$ for all $m\ge 0$, since $f\c[mi]=f\c[(m-1)i]\circ f\c[i]=f\c[(m-1)i]\circ x=f\c[(m-1)i]=x.$ Since there exists an $m$ for which $k+1\le mi\le k+n$, it follows that the product $$ \prod_{i=k+1}^{k+n} (f\c[i]-x) $$ contains a zero, so we are done.

Therefore, we can assume $f\c[i]\neq x$ for all $i\le n$. This means $$ \binom{n+k}n_f:=\frac{\prod_{i=k+1}^{k+n}(f\c[i]-x)}{\prod_{i=1}^n (f\c[i]-x)} $$ is a well defined element of the fraction field $A(x)$ of $A[x]$. We prove this is actually a polynomial by induction on $\min(n,k)$. The base case $\min(n,k)=0$ follows because when $n=0$, both products are empty so the ratio is $\frac11=1$, and when $n=k$, both products are equal so the ratio is again $1$. By straightforward algebraic manipulations, you can show when $\min(n,k)\ge 1$, then $$ \binom{n+k}n_f = \frac{f\c[(n+k)]-f\c[n]}{f\c[k]-x}\binom{n+k-1}n_f+\binom{n+k-1}{n-1}_f, $$

so by the induction hypothesis and Lemma 2, this is a polynomial.

Theorem 2

First, I claim that for any coprime integers $m,n$, we have the following equality of ideals: $$ \def\<{\langle}\def\>{\rangle}\<f\c[n]-x\> + \<f\c[m]-x\>=\<f-x\> $$ The proof is by induction on $\max(n,m)$, the base case where $\max(n,m)=1$ being obvious.

By Lemma 3, we have $f-x$ divides both $f\c[n]-x$ and $f\c[m]-x$, proving the inclusion $\<f\c[n]-x\> + \<f\c[m]-x\>\subseteq \<f-x\>$. For the other inclusion, assume that $n>m$, note that by induction we have $$ \<f-x\> =\<f\c[(n-m)]-x\>+\<f\c[m]-x\> \subseteq\<f\c[n]-f\c[(n-m)]\>+\<f\c[n]-x\>+\<f\c[m]-x\> $$ Since Lemma 2 impies $\<f\c[n]-f\c[(n-m)]\>\subset \<f\c[m]-x\>$, the claim follows.

The claim implies that $$ (f\c[n]-x)p(x)+(f\c[m]-x)q(x)=f-x $$ for some polynomials $p$ and $q$. Multiplying both sides by $(f\c[mn]-x)$, we get $$ (f\c[mn]-x)(f\c[n]-x)p(x)+(f\c[mn]-x)(f\c[m]-x)q(x)=(f-x)(f\c[mn]-x) $$ Since Lemma 3 implies $f\c[m]-x$ divides $f\c[mn]-x$, we have $(f\c[m]-x)(f\c[n]-x)$ divides $(f\c[mn]-x)(f\c[n]-x)p(x)$. Similarly, $(f\c[m]-x)(f\c[n]-x)$ divides $(f\c[mn]-x)(f\c[m]-x)q(x)$. Since $(f\c[m]-x)(f\c[n]-x)$ divides both summands on the LHS of the above equation, it divides the RHS, as desired.