猴子摘桃问题

问题符号化描述如下：

（约定以下全部讨论在$Z_+$值域内进行）
定义一函数 $F(x) = \frac{a-1}{a}(x-1)$，其中$a \gt 1$，显然这一函数并非对于所有$x$都在$Z_+$域内有意义，函数有意义的充要条件是$x\equiv1\pmod{a}$。
定义记号 $F_n(x)$表示对于$x$进行$n$次$F$变换，即：

$$F_n(x)=\begin{cases} x, & \text{ if } n = 0\\ F(F_{n-1}), & \text{ if } n \gt 0 \end{cases}$$
设对于某一确定$n$，所有使$F_n(x)$在$Z_+$域内有意义的$x$的集合为$T_n$，其中最小的$x$为$M_n$。
给出$a$、$n$，求$M_n$。

据说结论为$a^n-(a-1)$，但我找了一圈似乎没有特别好的证明，遂尝试自行说明。这是萌新的第一次证明，多有不足之处，还请大佬批评指教。更简单的方法应该还有，希望能抛砖引玉。

T1.1 $x \in T_n$，当且仅当$F(x) \in T_{n-1}$

T1.2 若$x \in T_n$，则$(x + a^n) \in T_n$

T1.3 在T1.2约定的条件下，不存在$x \lt y \lt x + a^n$且$y \in T_n$

T1.1正确性显然。T1.2利用数学归纳法说明如下：

$n = 1$时，结论正确性显然；

假设结论对于$n \le k - 1$成立，对于$n = k$，由于$x \in T_k$，由T1.1得$F(x) \in T_{k-1}$，而

$$F(x + a^k) = \frac{a-1}{a}(x + a^k - 1) = F(x) + \frac{a-1}{a}a^k = F(x) + (a - 1)a^{k-1}$$ ，由于$F(x) \in T_{k - 1}$，由归纳假设得$F(x) + (a - 1)a^{k-1} \in T_{k-1}$，即$F(x + a^k) \in T_{k-1}$，由T1.1得$(x + a^k) \in T_k$，归纳假设成立。

T1.3可利用反证法和数学归纳法说明：假设这样的$y$存在，则

$$0 < y - x < a^n，F(x) < F(y) < F(x) + (a-1)a^{k-1}$$
设$t = F(y) - F(x)$，由$F$函数性质可知$(a-1) | t$。又由于$t < (a-1)a^{k-1}$，有$\frac{t}{a-1} \lt a^{k-1}$。则由T1.1、T1.2可知存在$x' \in T_{k-1}$满足$x' \lt F(y) \lt x' + a^{k-1}$，由归纳假设得$F(y) \notin T_{k-1}$，这与$y \in T_k$相矛盾。故假设不正确，$y$不存在。

D1.1 将$x$在$a$进制下的表示中从右向左第$i$位设为$x[i]$。即，$x = \sum_{i}x[i] \times a^{i-1}$，且对于任意正整数$i$有$0 \le x[i] \lt a$。

在D1.1定义下，T1.2、T1.3可等价表述为：对于$x \in T_n$，$x' \in T_n$的充要条件是对于$1 \le i \le n$有$x[i] = x'[i]$，或称在$a$进制下它们的后$n$位相等。

T1.4 $M_1 = 1, M_k = M_{k-1} + (a - 1) \times a^{k - 1}$ ，或等价表述为：在$a$进制下$M_k$有$k$位，末位为$1$，其余各位为$(a-1)$

不妨用归纳法说明。显然$M_1 = 1$。
对于k，由于$M_k \in T_k$，显然$M_k \in T_{k-1}$，则有归纳假设我们有$M_k$末位为$1$，第$2$至$k-1$位均等于$(a-1)$。设第$k$位为$p$，更高位为$0$（显然当且仅当此时$M$为最小值），由$F$定义和$a$进制下基本运算定义知$F(M_k) = (M_k - 1) - \frac{1}{a}(M_k - 1)$，即原数去除末位减去去除末位后右移一位的值，则$F(M_k)$第$k-1$位值为$(a-1) - 1 - p$或$(a - 1) - 1 - p + a$（退位时）。由$M_k \in T_k$知$F(M_k) \in T_{k - 1}$，由归纳假设得$F(M_k)$第$k-1$位应为$(a-1)$，即：

$$(a-1) - 1 - p = a - 1$$ 或 $$(a - 1) - 1 - p + a = a - 1$$

解第一个方程得$p = -1$，舍去；解第二个方程得$p = a - 1$，即$M_k$第$k$位取值为$a-1$，归纳假设成立。

则根据T1.4，所求的答案即

$$M_n= 1 + \sum^{i \le n}_{i = 2}(a - 1)a^{i - 1} = a^n - (a - 1)$$