$n$ 次多项式在模质数 $p$ 的意义下最多有 $n$ 个解。

递归形式：对质数 $p$ 和正整数 $n,m$，有 $C_n^m\equiv C_{[n/p]}^{[m/p]}C_{n\bmod p}^{m\bmod p}\pmod{p}$。

进制形式：对质数 $p$ 和正整数 $n,m$，有 $C_n^m\equiv C_{n_{k-1}}^{m_{k-1}}C_{n_{k-1}}^{m_{k-1}}\cdots C_{n_0}^{m_0}\pmod{p}$。其中 $n_i,m_i\in \mathbb{Z}_p$，$n=\sum\limits_{i=0}^{k-1}n_ip^i$，$m$ 同理。

对于有限阶递归整数数列的（混）周期的证明，可以转而去证明一个等价条件：数列有界。

本题研究时可以发现 $k,l$ 互质的形式相对简单，$k,l$ 不互质时可以尝试变为互质情形。

引理：若 $\{x_n\}$ 有界，则 $\{x_n\}$ 有周期。

不妨设 $x_n=ky_n+l(l\in \mathbb{N}$，因为可以从 $x_2$ 算起，则有 $y_{n+2}=\gcd(ky_{n+1}+l,ky_n+l)$，$x$ 有界等价于 $y$ 有界。

若 $\gcd(k,l)=1$，则 $y_{n+2}=\gcd(ky_{n+1}+l,ky_n+l)=\gcd(k(y_{n+1}-y_n),ky_n+l)=\gcd(y_{n+1}-y_n,ky_n+l)\le|y_{n+1}-y_n|\le\max\{y_{n+1},y_n\}$，故 $y_n\le\max\{y_1,y_0\}$，即 $y$ 有界。

若 $\gcd(k,l)=d>1$，不妨设 $y_n=dz_n,z_n\in\mathbb{Z}^+,n\in\mathbb{N}$，因为可以从 $y_2$ 算起，则有 $z_{n+2}=\gcd(kz_{n+1}+l/d,kz_n+l/d)$，$y$ 有界等价于 $z$ 有界。

由于 $\gcd(k,l/d)\le l/d<l$，反复操作必有 $d=1$。故 $x$ 有界。

上述过程可以改写为对 $l$ 归纳。

对于含有 $\operatorname{mex}$ 定义的数列，可以考虑贝蒂(Beatty)定理的形式或者证明方式。

设 $\alpha=\dfrac{\sqrt{k^2+4}+2-k}{2},\beta=\dfrac{\sqrt{k^2+4}+2+k}{2}$，则 $\beta-\alpha=k,1/\alpha+1/\beta=1$。

由贝蒂(Beatty)定理，$[\alpha n]=\operatorname{mex}\limits_{i=1}^{n-1}\{[\alpha i],[\beta i]\}$，故可归纳证明 $f(n)=[\alpha n],f(n)+kn=[\beta n]$。

原命题即证 $[\alpha([\beta n]-n)]=[\beta n]-1$，

即 $[\beta n]-1\le \alpha([\beta n]-n)<[\beta n]$，

$\alpha n-1\le (\alpha-1)[\beta n]<\alpha n$，

$(\beta-1)(\alpha n-1)\le [\beta n]<(\beta -1)\alpha n$，

$\beta n-(\beta -1)\le [\beta n]<\beta n$。

由 $\beta>2$ 且 $\beta$ 为无理数知显然成立。

条件 2 很容易让人想到 Stern–Brocot 树与 Farey 序列，有理数的 $f$ 显然分母是 2 的幂，由于(第 $i$ 层的所有有理数)的 $f$ 把最简形式的分母为 $2^i$ 的有理数用完了，故无理数的 $f$ 不可能分母为 $2^i$。

先证对 $x=\dfrac{p}{q}, p,q\in\mathbb{N},p\le q,\gcd(p,q)=1$，有 $f(x)$ 的分母为 $2$ 的幂。

考虑对 $p+q$ 归纳。$p+q=1,2(x=0,1)$ 平凡。

若 $p+q>2$，考虑方程 $a(q-b)-b(p-a)=1$，即 $aq-bp=1$，显然其有 $0\le a<p,0\le b<q$ 的解，故存在非负整数 $a\le b\ne 0;c\le d\ne 0$ 满足 $|ad-bc|=1$，$a+c=p$ 和 $b+d=q$。

由归纳假设，$f(\dfrac{a}{b}),f(\dfrac{c}{d})$ 的分母均为 $2$ 的幂，故 $f(\dfrac{p}{q})=f(\dfrac{a+c}{b+d})=\dfrac{f(\dfrac{a}{b})+f(\dfrac{c}{d})}{2}$ 的分母也为 $2$ 的幂。

再证对所有的 $i\in\mathbb{N}$ 和 $0\le p\le 2^i$，存在有理数 $x$，使得 $f(x)=\dfrac{p}{2^i}$。进而由 $f$ 单调递增，知 $f$ 是单射。

同时我们归纳：$f(\dfrac{a}{b})=\dfrac{p}{2^i},f(\dfrac{c}{d})=\dfrac{p+1}{2^i}$，则 $|ad-bc|=1$。

$i=0$ 平凡。

$i>0$ 时，不妨设 $2\nmid p$，$f(\dfrac{a}{b})=\dfrac{\frac{p-1}{2}}{2^{i-1}},f(\dfrac{c}{d})=\dfrac{\frac{p+1}{2}}{2^{i-1}}$，则 $f(\dfrac{a+c}{b+d})=\dfrac{p}{2^i}$，且 $|a(b+d)-b(a+c)|=|(a+c)d-(b+d)c|=|ad-bc|=1$。

由于有理数在实数中稠密，分母为 $2$ 的幂的有理数也在实数中稠密，故单调性可以推出连续性。

考虑用有理数 $x$ 近似 $\sqrt{2}-1$，为使 $f(x)$ 有规律，可以想到用连分数近似（二次代数数的连分数有循环）。

事实上，也可也可以直接观察到 $\sqrt{2}-1$ 的 Farey 二进制为 LLRRLLRR……

答案为 $\dfrac{2}{5}$。

取 $x_0=0,y_0=1,x_{n+1}=\dfrac{1}{x_n+2},y_{n+1}=\dfrac{1}{y_n+2}$，则 $\min\{x_n,y_n\}<\sqrt{2}-1<\max\{x_n,y_n\}$，且 $\min\{x_n,y_n\},\max\{x_n,y_n\}\to\sqrt{2}-1$。

对有理数 $x=\dfrac{a}{b}(\gcd(a,b)=1),y=\dfrac{c}{d}(\gcd(c,d)=1)$，记 $x\oplus y=\dfrac{a+c}{b+d}$，可以归纳证明 $x_{n+1}=x_n\oplus y_n, y_{n+1}=x_n\oplus x_{n+1}$。

所以 $f(x_{n+1})=\dfrac{1}{2}f(x_n)+\dfrac{1}{2}f(y_n),f(y_{n+1})=\dfrac{1}{2}f(x_n)+\dfrac{1}{2}f(x_{n+1})=\dfrac{3}{4}f(x_n)+\dfrac{1}{4}f(y_n)$。

解得 $f(x_n)=\dfrac{2}{5}-\dfrac{2}{5}(-\dfrac{1}{4})^n,f(y_n)=\dfrac{2}{5}+\dfrac{3}{5}(-\dfrac{1}{4})^n$。

由于 $\min\{f(x_n),f(y_n)\}=f(\min\{x_n,y_n\})<f(\sqrt{2}-1)<f(\max\{x_n,y_n\})=\max\{f(x_n),f(y_n)\}$，且 $\min\{f(x_n),f(y_n)\},\max\{f(x_n),f(y_n)\}\to\dfrac{2}{5}$，故 $f(\sqrt{2}-1)=\dfrac{2}{5}$。