强行归纳

xcx

数列 $\{x_n\}$ 满足 $x_1=1,x_{n+1}=1+\frac{n}{x_n}$
证明其中只有前三项为整数

Czhang271828

已修改.

首先断言在 $n\geq 4$ 时 $x_n$ 单调递增. 实际上, $n\geq 4$ 时总有
$$
\dfrac{1}{2}+\sqrt{n-\dfrac{3}{4}}< x_n < \dfrac{1}{2}+\sqrt{n+\dfrac{1}{4}}.
$$
若存在极小的 $n_0\geq 4$ 使得 $x_{n_0+1}$ 为整数, 注意到有等式
$$
n_0!=(x_{n_0+1}-1)\cdot \prod _{n=2}^{n_0} x_n(x_n-1).
$$
其中 $x_n$ 在 $4\leq n\leq n_0$ 时均为形如 $\dfrac{p_n}{q_n}$ 的既约正有理数, 则
$$
4\cdot \prod_{n=4}^{n_0} (p_n-q_n)p_n\mid n_0!.
$$
再估计 $p_n$. 对 $4\leq n<n_0$ 总有 $q_n\neq 1$, 从而
$$
p_n\geq 2\left\lfloor\dfrac{1}{2}+\sqrt{n-\dfrac{3}{4}}\right\rfloor\geq 2\lfloor\sqrt{n}\rfloor.
$$
从而有不等式(注意到 $(p_{n_0}-q_{n_0})p_{n_0}$ 的放缩程度为其他项的 $\dfrac{1}{4}$, 因为 $q_{n_0}$ 可能为 $1$)
$$
4\prod_{n=4}^{n_0} (p_n-q_n)p_n\geq \prod_{n=4}^{n_0}\lfloor \sqrt n\rfloor\cdot 2\lfloor \sqrt n\rfloor\geq 2^{n_0-3}\prod_{n=4}^{n_0}\lfloor \sqrt n\rfloor ^2.
$$
而另一方面, 上式左侧为 $n_0!$ 的因子, 从而至少有
$$
2^{n_0-3}\prod_{n=4}^{n_0}\lfloor \sqrt n\rfloor ^2\leq n_0!.
$$
然而上式在 $n_0\geq 9$ 时不再成立, 此后 $2\lfloor \sqrt x\rfloor ^2> x$ 也是显然的.

题外话, 最后一个不等式暗示 $q_n$ 的增长速率也是大于等于 $2^n$ 量级的.

kuing

Czhang271828 发表于 2023-1-7 13:29
注意到 $n\geq 4$ 时,
$$
n!=\prod_{k=1}^ n(x_{k+1}-1)x_k=(x_{k+1}-1)\cdot \prod_{k=2}^ nx_k (x_k-1).

第二个等号后面打错了，应该是 `(x_{n+1}-1)`

后面 “故 $\dfrac{n!}{x_{n+1}-1}$ 为整数, 且包含因子 $2^{n-1}$” 我没看懂

xcx

感谢2#优秀的做法 标答给的无厘头放缩考场上实在难以想到 想估阶在n不充分大时也不够紧

xcx

给出一个刚得到的偏数论的做法
记 $\displaystyle x_n=\frac{a_n}{a_{n-1}}$，则有 $a_{n+1}=a_n+na_{n-1},a_0=a_1=1$
考虑指数型母函数 $\displaystyle f(x)=\sum_{n\geq0}{\frac{a_n}{x!}x^n}$，我们有 $f'(x)=(1+x)f(x)$
结合 $f(x)=0$ 我们有 $ f(x)=exp\{x+\frac{x^2}2\}$
那么我们有 $\displaystyle a_n= \sum_{k=0}^{\lfloor n / 2\rfloor}\binom{n}{2k}(2k)!!$
我们接下来证明 $gcd(a_n,a_{n+1})$ 必为 $2$ 的方幂
事实上, 我们设奇素数 $p \mid a_n, a_{n+1}$ 且 $p \nmid a_{n-1}$
那么我们有 $p \mid n$，然而在 $a_n$ 通项中若 $p \mid n$, 则 $\left(\begin{array}{c}n \\ 2 k\end{array}\right)$ 在 $p \nmid k$ 时为 $p$ 的倍数
而 $(2 k) !$ ! 在 $p \mid k$ 且 $k>0$ 时为 $p$ 的倍数. 因此当 $p \mid n$ 时 $a_n \equiv 1(\bmod p)$，矛盾!
再接下来我们注意到 $a_n$ 与 $a_{n+1}$ 的最大公约数整除 $n$ !
由于这个最大公约数为 $2$ 的方幂, 我们有 $\left(a_n, a_{n+1}\right) \mid 2^{n-1}, \forall n \geq 1$
然而 $a_n \geq(2\lfloor n / 2\rfloor) !!$ 远比 $2^{n-1}$ 大, 这样我们就证明了对充分大的 $n, a_n \nmid a_{n+1}$, 即 $x_{n+1}$ 非整数
证毕！

事实上我们也得到了二楼的结论，即 $x_{n+1}$ 的最简分母 $\frac{a_n}{\left(a_n, a_{n+1}\right)}$ 随着 $n$ 趋于无穷, 且其增长速度比指数快

xcx

xcx 发表于 2023-1-7 20:54
感谢2#优秀的做法 标答给的无厘头放缩考场上实在难以想到 想估阶在n不充分大时也不够紧 ...

标答懒得敲了 就是对2#的放缩式归纳证明 并没有给出思路

Czhang271828

xcx 发表于 2023-1-7 21:16
给出一个刚得到的偏数论的做法
考虑母函数 $\displaystyle f(x)=\sum_{n\geq0}{\frac{a_n}{x!}x^n}$，我们 ...

谢谢回复. 我不大懂你们竞赛用的母函数之类的, 但结合上下文, $\dfrac{a_n}{x!}$ 有笔误?

后面似乎还有几个笔误. 个人对这套理论十分陌生, 希望答主可以将解答稍稍修复一下, 不然完全看不懂 QAQ. 再者, 能否给个题目出处?

xcx

Czhang271828 发表于 2023-1-7 21:55
谢谢回复. 我不大懂你们竞赛用的母函数之类的, 但结合上下文, $\dfrac{a_n}{x!}$ 有笔误?

后面似乎还有 ...

已修复 题目出处是浙江今年一套模拟卷 好像是湖州中学吧 出现在单选第八题 设问是有几个整数

Czhang271828

顺便提一下, $x_n=\sqrt n+1-\gamma+\mathcal O(\sqrt n^{-1})$, $\gamma=0.57\ldots$ 为 Euler 常数.

睡神

这个$n＞2$时$x_n$单调递增，怎么破？硬是没弄出来

睡神

xcx 发表于 2023-1-7 21:20
标答懒得敲了 就是对2#的放缩式归纳证明 并没有给出思路

思路就是列举几项，发现$n>2,x_n$单增，然后利用单增求出$x_n$的范围，但证明不出单增，只能上数归强行证明$x_n$的范围，有这个范围，后面就轻而易举了。
比如可以如下装逼：

可以证得$x_{n+1}>x_n\ge2,n\ge3$  

由$x_{n+1}=1+\dfrac{n}{x_n}>x_n$得$x_n<\dfrac{1}{2}+\sqrt{n+\dfrac{1}{4}},n\ge3$   

$x_{n-1}=\dfrac{n-1}{x_n-1}<x_n$得$x_n>\dfrac{1}{2}+\sqrt{n-\dfrac{3}{4}},n\ge4$

所以$\dfrac{1}{2}+\sqrt{n-\dfrac{3}{4}}<x_n<\dfrac{1}{2}+\sqrt{n+\dfrac{1}{4}},n\ge4$

变形得：$4n-3<(2x_n-1)^2<4n+1$   (1)

假设$n\ge4$时，存在$x_n$为正整数，则$2x_n-1$为奇数，$(2x_n-1)^2\equiv 1\pmod{4}$

此时，(1)式无解，矛盾

所以$n\ge4$时，不存在$x_n$为正整数

睡神

依题意可得：$x_n=1+\dfrac{{n-1}}{{1+ \dfrac{{n-2}}{{1+ \dfrac{{n-3}}{{1+ \dfrac{{n-4}}{\ddots\dfrac{2}{1+\dfrac{{1}}{1}}}}}}}}}$

最近一直在思考何版的连分数余项的那个问题，蓦然回首，发现此题的通项好像与连分数有点点关联，不过不是简单的连分数，而是一个高斯连分数。我就在想，能否用连分数的思路去分析$x_n$的单调性呢？下面进行试试就逝世系列...

设$x_n=\dfrac{p_n}{q_n}$为非既约分数，

则有$p_{n+1}=p_n+np_{n-1},q_{n+1}=q_n+(n-1)q_{n-1}$且$p_n=q_{n+1}$，其中$p_0=q_0=0,p_1=q_1=1$

$\therefore x_{n+1}-x_n=1+\dfrac{n}{x_n}-x_n=1+\dfrac{nq_n}{p_n}-\dfrac{p_n}{q_n}=\dfrac{nq^2_n+p_nq_n-p^2_n}{p_nq_n}$

$=\dfrac{nq^2_n+q_nq_{n+1}-q^2_{n+1}}{p_nq_n}=\dfrac{nq^2_n+q_{n+1}(q_n-q_{n+1})}{p_nq_n}=\dfrac{nq^2_n-(n-1)q_{n-1}q_{n+1}}{p_nq_n}$

假设存在$x_{n+1}<x_n \Longrightarrow nx_{n+1}<nx_n$                 (1)

则$nq^2_n<(n-1)q_{n-1}q_{n+1} $

$\Longrightarrow nx_{n-1}=\dfrac{np_{n-1}}{q_{n-1}}=\dfrac{nq_n}{q_{n-1}}<\dfrac{(n-1)q_{n+1}}{q_n}=\dfrac{(n-1)p_n}{q_n}=(n-1)x_n$

即$ (n+1)x_n<nx_{n+1} $，与(1)式矛盾

$ \therefore x_{n+1}\ge x_n $

哇塞！什么鬼！居然没逝世哇！弄出来了...

想的不容易，写的也不容易，喜欢的朋友请赏个赞吧😍😍😍

hbghlyj

Czhang271828 发表于 2023-1-7 13:55
但结合上下文, $\dfrac{a_n}{x!}$ 有笔误?

是啊！应该是$\dfrac{a_n}{n!}$
generatingfunctionology

Exponential generating function (EGF)

The exponential generating function of a sequence a_n is

$ {\displaystyle \operatorname {EG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.} $

Exponential generating functions are generally more convenient than ordinary generating functions for combinatorial enumeration problems that involve labelled objects.^[3]

Another benefit of exponential generating functions is that they are useful in transferring linear recurrence relations to the realm of differential equations. For example, take the Fibonacci sequence {f_n} that satisfies the linear recurrence relation f_n+2 = f_n+1 + f_n. The corresponding exponential generating function has the form

$ {\displaystyle \operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}} $

and its derivatives can readily be shown to satisfy the differential equation EF″(x) = EF′(x) + EF(x) as a direct analogue with the recurrence relation above. In this view, the factorial term n! is merely a counter-term to normalise the derivative operator acting on xⁿ.

hbghlyj

xcx 发表于 2023-1-7 14:26
已修复

但$\dfrac{a_n}{n!}$没有修复啊…

零定义

睡神 发表于 2024-4-9 01:28
依题意可得：$x_n=1+\dfrac{{n-1}}{{1+ \dfrac{{n-2}}{{1+ \dfrac{{n-3}}{{1+ \dfrac{{n-4}}{\ddots\dfrac{ ...

其实连分数这东西也不难理解

比如：$\dfrac{p_{n+1}}{q_{n+1}}=1+\dfrac{n}{\dfrac{p_n}{q_n}}=1+\dfrac{nq_n}{p_n}=\dfrac{p_n+nq_n}{p_n}$

$\Rightarrow p_{n+1}=p_n+nq_n,q_{n+1}=p_n$

$\Rightarrow p_{n+1}=p_n+np_{n-1},q_{n+2}=q_{n+1}+nq_n$

$\Rightarrow q_{n+1}=p_n+(n-1)q_{n-1}$

hbghlyj

xcx 发表于 2023-1-7 13:16
记 $\displaystyle x_n=\frac{a_n}{a_{n-1}}$，则有 $a_{n+1}=a_n+na_{n-1},a_0=a_1=1$
...
那么我们有 $\displaystyle a_n= \sum_{k=0}^{\lfloor n / 2\rfloor}\binom{n}{2k}(2k)!!$

$x_n=1+\text{ContinuedFractionK}[n-k,1,\{k,1,n-1\}]$
1+ContinuedFractionK[n-k,1,{k,1,n-1}]
Donald Knuth, The Art of Computer Programming, Volume III[Sorting and searching], §5.1.4 (page 62)
math.stackexchange.com/questions/758900/
Let $I(n)$ be the number of involutions in the symmetric group $S_n$, (i.e. $\sigma\in S_n$ such that $\sigma^2=I$). It is well-known that $I(n)$ can be calculated inductively by
$$
I(0)=I(1)=1,\qquad I(n+1)=I(n)+nI(n-1)
$$
This shows that our sequence $\{a_n\}$ is related to these numbers by the formula
$$a_n=\frac{I(n+1)}{I(n)}.$$
So, we can use what we know about these numbers, In particular, the following asymptotic expansion, from Knuth's book:
$$
I(n+1)=\frac{1}{\sqrt{2}} n^{n/2}e^{-n/2+\sqrt{n}-1/4}\left(1+\frac{7}{24\sqrt{n}}+{\cal O}\left(\frac{1}{n^{3/4}}\right)\right).
$$

Now, it is a "simple" matter to conclude from this that $a_n$ has the desired asymptotic expansion.

Edit: In fact the term $\mathcal{O}(n^{-3/4})$ effectively destroys the asymptotic expansion as @mercio noted, But in fact we have
$$
I(n+1)=\frac{1}{\sqrt{2}} n^{n/2}e^{-n/2+\sqrt{n}-1/4}\left(1+\frac{7}{24\sqrt{n}}+{\cal O}\left(\frac{1}{n}\right)\right).
$$
This is shown by WIMP AND ZEILBERGER in their paper ``Resurrecting the Asymptotics of Linear Recurrences''

hbghlyj

Czhang271828 发表于 2023-1-7 05:29
实际上, $n\geq 4$ 时总有
$$
\dfrac{1}{2}+\sqrt{n-\dfrac{3}{4}}< x_n < \dfrac{1}{2}+\sqrt{n+\dfrac{1}{4}}.
$$

按照您这个式子，应该有$$x_n-\sqrt{n}\to\frac12$$
但后面讲到

Czhang271828 发表于 2023-1-8 13:13
顺便提一下, $x_n=\sqrt n+1-\gamma+\mathcal O(\sqrt n^{-1})$, $\gamma=0.57\ldots$ 为 Euler 常数. ...

那么$$x_n-\sqrt n\to1-\gamma$$
这个常数$1-\gamma$应该是$\frac12$吧

hbghlyj

睡神 发表于 2024-4-10 01:04
数论那个，n充分大时，$x_n$为非整数，充分大是多大？不充分大时呢？

他说的充分大应该是当$a_n>2^{n-1}$时吧

xcx 发表于 2023-1-7 13:16
然而 $a_n \geq(2\lfloor n / 2\rfloor) !!$ 远比 $2^{n-1}$ 大, 这样我们就证明了对充分大的 $n, a_n \nmid a_{n+1}$, 即 $x_{n+1}$ 非整数