"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 .

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$
