"Binomial coefficients" generalized via polynomial iteration 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 .
 A: 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$
A: 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.
