摘要 本文是关于开普勒第一定律, 即有界行星轨道是椭圆形的初等证明, 无需使用微积分. 这个证明在精神上与前人的推导类似, 运用守恒定律获得行星轨道的表达式, 然后将其与椭圆的方程进行比较. 然而, 我们从椭圆的两个众所周知的性质中, 使用三角学推导出匹配行星轨道的方程. 完全避免了微积分.

关键词 开普勒第一定律; 椭圆; 三角函数

一、导言

牛顿对行星轨道的解释是他的运动定律和万有引力定律的重大胜利之一. 在高中和大学的基础物理教科书中, 关于万有引力的章节总是描述开普勒的行星运动三定律, 但大多数教科书只推导出圆形轨道的结果. 避免微积分的证明是一种有价值的教学辅助工具, 对物理学学生和热衷的业余物理学家和天文学家都有吸引力. 其他人已经提供了一些基于微积分、几何或代数和三角学的初等推导. 如 E. Vogt (1996年); Noll(2002年); Goodstein 和 Goodstein(1996年); Provost 和 Bryant(2009年); Unruh(2018)然而, 文献中看到的分析推导往往会将动力学方程简化为学生或爱好者在课程中通常不会遇到的椭圆方程, 并且该方程描述椭圆的理由要么被视为标准的数学结果, 如 Noll(2002), 要么通过应用微积分推导出, 如 E.Vogt(1996).

在这项工作中, 我们采用了一个不寻常的椭圆方程来证明该定律. 我们运用三角函数从两个众所周知的特质来推导这个方程. 然后, 这个方程很容易与通过将守恒定律应用于物理问题而导出的方程相匹配, 表明轨道是椭圆形的. 因此, 我们相信, 我们在这项工作中得出结果的假设应该是高中生或爱好者相对容易接受的.

二、能量守恒和角动量守恒

守恒定律在描述系统的动力学中起着重要的作用, 它为我们提供了运动常数. 事实上, 如果能够确定足够数量的独立运动常数, 就可以完整地描述系统的动力学.

在开普勒问题中有三个守恒量, 但我们在这里只关心其中的两个, 能量和角动量.

为了简化开普勒问题, 我们假设其中一个天体(“太阳”)的质量 $M$ 远远大于另一个天体(“行星”)的质量 $m$, 以至于可以将其视为在空间中静止不动 (注: 如果需要, 可以使用相对坐标和约化质量的公式来克服这种近似). 将 $M$ 放在原点, 让我们用向量 $\vec{r}$ 表示运动天体 $m$ 的位置, 用向量 $\vec{v}$ 表示其速度. 设 $\phi$ 为从 $\vec{r}$ 逆时针转向 $\vec{v}$ 的角度. 如下图 FIG.1

一个表示所考虑的物理系统的图形. 物体 $m$ 环绕另一个物体 $M \gg m$ 运动. 原点与 $M$ 的位置重合, $M$ 被近似认为静止的. $m$ 的速度用向量 $\vec{v}$ 表示, 其位置用向量 $\vec{r}$ 表示. 向量 $\vec{v}$ 作为 $m$ 轨迹的切线, 与向量 $\vec{r}$ 形成一个角度 $\phi$.

然后我们可以把物体的角动量写成

$$ \label{eq:AngularMomentum} \vec{L} = m \vec{r} \times \vec{v} = m r v \sin \phi \hat{z},\tag{1} $$

其中, $r$ 和 $v$ 分别表示 $\vec{r}$ 和 $\vec{v}$ 的模大小, 并且 $\hat{z}$ 是在垂直于 $\vec{r}$ 和 $\vec{v}$ 的方向上的单位矢量. 由于作用在物体 $m$ 上的重力沿着连接物体的线作用, 所以没有扭矩施加在物体上, 从而角动量 $\vec{L}$ 在大小 $L$ 和方向 $\hat{z}$ 上都守恒. 方向的恒定性告诉我们, 轨迹必须位于垂直于 $\hat{z}$ 的平面内.

由于没有非保守力作用在物体 $m$ 上, 系统的能量 $E$ 也是运动常数. 它由动能和重力势能的总和给出,

$$ E = \frac{1}{2} m v^2 - \frac{G M m}{r}, \label{eq:energy}\tag{2} $$

其中 $G$ 是万有引力常数. 请注意, 我们遵循的约定是在势能平面无穷远时引力势能为 $0$, 这样一来, 有界轨道的总能量 $E$ 将是负的(因为这样的物体没有足够的能量到达无穷远). 我们在这里的处理仅限于有界轨道的情况.

三、由守恒定律导出的轨道方程

对 $v$ 求解方程 $\eqref{eq:energy}$, 可以得到

$$ \label{eq:Velocity} v = \sqrt{\frac{2E}{m} + \frac{2GM}{r}}. \tag{3} $$

代入方程 $\eqref{eq:AngularMomentum}$, 可以得到

$$ \label{eq:PreTrajectory} L = m \sin \phi \sqrt{\frac{2Er^2}{m} + 2 G M r}, \tag{4} $$

整理可得

$$ \begin{equation} \label{eq:Trajectory} \left ( r^2 + \frac{GMm}{E} \, r \right ) \sin^2 \phi = \frac{L^2}{2mE}. \tag{5} \end{equation} $$

上述方程告诉我们, 位置向量和速度向量之间的夹角 $\phi$ 如何随着距离 $r$ 变化. 注意到速度向量是轨迹的切线, 我们将 $\phi$ 定义为行星位置向量的切线所成的角度. 因此, 原则上, 方程 $\eqref{eq:Trajectory}$ 描述了行星所处的轨道. 然而, 它使用的是不常见的变量, 因此不能立即与已知的椭圆标准方程相匹配.

注释内容(非正文部分)

我们现在注意到方程 $\eqref{eq:Trajectory}$ 告诉我们, 行星与太阳之间存在一个最小距离 $r_p$(称为近日点距离). 我们可以通过以下方式得出这个结论: 我们重新排列方程如下:

$$ \begin{equation} \label{eq:TrajectoryRearranged} E r^2 + GMmr = \frac{L^2}{2m \sin^2 \phi}, \end{equation} $$

并且注意到如果 $r > 0$ 变得足够小, 方程的左边会变得足够小, 以至于我们最终会得到一个荒谬的要求, 即 $\sin^2 \phi > 1$. 这个结论不受 $E \lesseqqgtr 0$ 的影响, 因为对于足够小的 $r$, $E r^2$ 项小于 $GMmr$ 项. 我们同样注意到, 当 $E < 0$ 时, $r$ 也有一个上限(远日点距离), 因为如果 $r$ 变得非常大, $E r^2$ 项会变得足够负, 以至于左边也会变得负的, 最终得到另一个荒谬的要求, 即 $\sin^2 \phi < 0$. 从这个方程推导出近日点和远日点距离的过程被放在附录中.

由于上述对曲线的描述相当不寻常, 我们详细阐述一下如何根据上述方程绘制轨迹: (注: 请注意, 这种方法在实践中并不是一个好方法, 因为由于有限步长 $\varepsilon$ 引起的误差会累积. 只有在 $\varepsilon \to 0$ 的极限情况下, 这种方法才能得到正确的轨迹)

• 在纸上标记一个点, 并将其称为 $F$. 这将标记太阳的位置.
• 选择任意一个起始点 $P_0$, 它距离 $F$ 的距离为 $r_0$, 在前一段讨论的允许范围内选择任意一个 $r_0$ 的值; 为了画图的简便, 让我们从一个距离最短的允许点开始, 即近日点距离 $r_p$, 位于 $F$ 的右侧. 让我们称这个点为 $P_0$. 标记这个点.
• 通过在方程 $\eqref{eq:Trajectory}$ 中代入 $r = r_0$ 来计算角度 $\phi$. 方程无法唯一确定角度 $\phi$, 因此选择 $0^\circ$ 到 $90^\circ$ 之间的解, 从轨迹的上半部分开始.
• 从太阳位置 $F$ 画一条线穿过点 $P_0$, 在 $P_0$ 处逆时针测量角度 $\phi$, 并在所得到的方向上画一条微小的线段(长度 $\varepsilon$), 以得到下一个点 $P_1$.
• 现在测量点 $P_1$ 到 $F$ 的距离 $r_1$.
• 通过将 $r_1$ 代入方程 $\eqref{eq:Trajectory}$ 来得到 $\phi_1$ 和点 $P_2$, 然后继续重复这个过程, 逐步描绘出整个轨迹.

熟悉微积分的读者会识别出上述过程实际上就是数值积分. 实际上, 方程 $\eqref{eq:Trajectory}$ 是轨迹的一阶微分方程, 因为它(宽泛地说)根据给定点处切线的斜率来指定曲线. 因此, 如果不直接使用微积分, 或者以有限差分的一阶近似的形式, 提供一个直接推导来证明轨迹是椭圆、双曲线或抛物线将是具有挑战性的, 如果不是不可能的话. 这项工作反而采取了分别推导出椭圆方程并将其与方程 $\eqref{eq:Trajectory}$ 匹配的方法, 我们将在下一节完成这项任务. 导数关系也许是我们推导椭圆方程时假设两个性质而不是一个的原因——这两个性质结合起来提供了切线斜率与曲线上位置之间的关系. 因此, 结果在代数操作上更为简洁, 视觉上也更直观.

四、用切线描述椭圆的方程

在本节中, 我们将推导出一个不寻常的椭圆方程, 当与方程 $\eqref{eq:Trajectory}$ 匹配时, 将立即导出开普勒的第一定律. 让我们用 $a$ 表示椭圆的半长轴, 用 $e$ 表示其偏心率. 偏心率 $e$ 的一个定义是, 焦点位于椭圆中心的两侧, 距离为 $ae$. 由于焦点位于椭圆内部, 所以 $0 \leq e < 1$, 当 $e = 0$ 时, 对应的是焦点重合的情况, 即圆形.

考虑 FIG.2, 其中我们用 $F'$ 和 $F$ 表示椭圆的两个焦点. 我们首先明确椭圆的两个重要性质.

1. 给定椭圆上的任意一点 $P$, 长度 $|PF'|$ 和 $|PF|$ 的和是常数, 且等于 $2a$.

2. 如果一个镜子做成了椭圆的形状(在椭圆平面的垂直方向上有一小部分延伸), 从焦点 $F$ 发出的一束光线, 击中椭圆上的任意一点 $P$ 后, 会反射到另一个焦点 $F'$, 反之亦然. 数学上, 这意味着椭圆在点 $P$ 处的法线平分角度 $FPF'$, 因为入射角和反射角(从法线测量)必须相等.

注: 这两个性质不是相互独立的. 第二个性质可以通过第一个性质推导出来, 例如, 通过使用费马原理. 然而, 同时使用这两个性质可以让我们简化代数运算并避免使用微积分.

图示 FIG.2 与方程 $\eqref{eq:PedalEquation}$ 的推导相关, 这是对椭圆的一个非传统描述, 关联了 $r$ 和 $\phi$. 点 $C$ 是椭圆的中心, $F'$ 和 $F$ 是焦点. 椭圆的半长轴为 $a$, 偏心率为 $e$. 焦点之间的距离是 $2ae$, 而从焦点到椭圆上任意一点 $P$ 的距离之和是 $2a$.

现在我们准备推导我们寻求的方程. 在 FIG.2 中, 椭圆在点 $P$ 处的切线被表示为线段 $TT'$, 法线被表示为线段 $NN'$. 让我们用 $\phi$ 表示线段 $FP$ 与切线 $T'T$ 之间的角度. 由于到每个焦点的距离是 $ae$, 线段 $F'F$ 的长度是 $2ae$. 让我们用 $r$ 表示长度 $|PF|$. (注: 我们在本节中重新使用符号 $\phi$ 和 $r$ 是有意的: 我们稍后将看到这些确实对应于前一节中的相应符号. )

那么根据性质 (1), $|PF'| + |PF| = 2a$, 或者 $|PF'| = 2a - r$. 由于 $TT'$ 和 $NN'$ 垂直, $\angle NPF$ 是 $90^\circ - \phi$. 使用性质 (2), 我们有 $\psi = 2(90^\circ - \phi) = 180^\circ - 2\phi$. 通过将余弦定理应用于三角形 $F'PF$, 我们得到 $$ \begin{equation} \label{eq:CosineRule} (2ae)^2 = (2a - r)^2 + r^2 - 2r(2a - r) \cos(180^\circ - 2\phi). \tag{6} \end{equation} $$ 使用三角恒等式 $\cos(180^\circ - \theta) = -\cos\theta$ 和 $\cos 2\theta = 1 - 2\sin^2 \theta$, 并对结果进行简化, 我们得到 $$ \begin{equation} \label{eq:PedalEquation} \begin{aligned} % (2ae)^2 =& (2a - r)^2 + r^2 + 2r(2a - r) (1 - 2\sin^2 \phi)\\ % =& (2a)^2 + 4ar + r^2 + r^2 + 2r(2a - r) - 4r(2a - r)\sin^2 \phi\\ % =& (2a)^2 + (2ar - r^2) \sin^2 \phi\\ % a^2 (1 - e^2) =& (2ar - r^2) \sin^2 \phi. (r^2 - 2ar) \sin^2 \phi = -a^2 (1 - e^2). \end{aligned} \tag{7} \end{equation} $$ 上述关联 $r$ 和 $\phi$ 的方程描述了一个半长轴 $a > 0$ 且偏心率 $0 < e < 1$ 的椭圆. (注: 在方程 $\eqref{eq:PedalEquation}$ 中代入 $\sin \phi = p / r$ 会得到椭圆的*切点方程*, 但我们更倾向于保持当前的形式以便于几何直觉的理解. ) 如果我们代入 $e = 0$, 它也描述了一个圆. 但这一点不太容易看出来: 注意到表达式 $2ar - r^2$ 和 $\sin^2 \phi$ 的最大值分别是 $a^2$ 和 1, 我们可以看到右边只能通过 $r = a$ 和 $\sin \phi = \pm 1$ 来达到等于 $-a^2$ 的值, 这确实描述了一个圆.

五、开普勒第一定律: 椭圆轨道, 当 $E < 0$

现在我们将第三节的物理结果与第四节的数学结果联系起来. 让我们将 FIG.2 中的点 $P$ 和 $F$ 分别与某一时刻天体 $m$ 的位置和天体 $M$ 的位置等同起来. 然后我们可以将方程 $\eqref{eq:Trajectory}$ 中的 $r$ 和 $\phi$ 与 FIG.2 中的相应符号对应起来. 如果我们现在比较方程 $\eqref{eq:Trajectory}$ 和方程 $\eqref{eq:PedalEquation}$, 我们会发现如果它们确实是相同的, 那么 $$ \begin{equation} \label{eq:Identifications} \begin{aligned} a \;=&\; -\frac{GMm}{2E},\\ e \;=&\; \sqrt{1 + \frac{2EL^2}{(GM)^2 m^3}}. \end{aligned} \tag{8} \end{equation} $$ 因此, 我们已经证明了当 $E < 0$ 时, 天体 $m$(“行星”)的轨迹是一个椭圆, 天体 $M$(“太阳”)位于椭圆的一个焦点上, 其半长轴 $a$ 和偏心率 $e$ 是通过方程$\eqref{eq:Identifications}$ 由物理参数和运动常数确定的. 半长轴 $a$ 和偏心率 $e$ 的值与教科书中推导出的结果一致. 给定初始条件, 我们可以计算角动量 $\vec{L}$ 和能量 $E$, 从而确定椭圆的形状和方向.

如果 $E > 0$ 或 $E = 0$, 我们无法在满足约束条件 $a > 0$ 和 $0 \leq e < 1$ 的情况下, 将方程 $\eqref{eq:Trajectory}$ 的形式与方程 $\eqref{eq:PedalEquation}$ 匹配. 因此, 在这些情况下, 轨迹不是椭圆. 对于 $E > 0$ 和 $E = 0$ 的情况, 同样可以推导出类似于方程 $\eqref{eq:PedalEquation}$ 的方程, 分别对应于双曲线和抛物线, 我们可以将方程 $\eqref{eq:Trajectory}$ 和方程 $\eqref{eq:PreTrajectory}$ 与它们匹配.

六、开普勒第二定律: 相等时间内扫过相同面积(注释部分)

这个定律的基本推导是众所周知的, 并且在大多数基础物理教科书中都会介绍一般轨道(不仅仅是圆形轨道). 我们在这里为了完整性和它在获得第三定律方面的有用性而呈现它.

在某个瞬间, 让天体 $m$ 位于其轨迹上的一个位置 $\vec{r}$. 在一小段时间 $\mathrm{d}t$ 内, 天体沿着一个微小的椭圆形弧移动到位置 $\vec{r'}$, 在原点($F'$)处形成一个角度 $\mathrm{d}\theta$. 通过将这个弧近似为圆弧, 我们可以将这样定义的圆形扇形的面积写为 $\mathrm{d}A = \frac{1}{2} r^2 \mathrm{d}\theta$, 在其中我们忽略了 $\vec{r}$ 和 $\vec{r'}$ 之间大小的变化.

从角动量的表达式 $\eqref{eq:AngularMomentum}$, 我们认识到 $v \sin \phi$ 是 $\vec{v}$ 垂直于 $\vec{r}$ 的分量的大小, 它描述了方向变化的速率, 即, $$ \begin{equation*} v \sin \phi = r \:\frac{\mathrm{d}\theta}{\mathrm{d}t}. \end{equation*} $$ 因此, 我们注意到 $$ \begin{equation} \label{eq:SecondLaw} \begin{aligned} \frac{\mathrm{d}A}{\mathrm{d}t} =& \frac{1}{2} r^2 \frac{\mathrm{d}\theta}{\mathrm{d}t}\\ =& r v \sin \phi\\ =& \frac{L}{m}. \end{aligned} \end{equation} $$ 由于 $L/m$ 是常数, 我们有 ${\mathrm{d}A}/{\mathrm{d}t}$ 是常数, 因此位置向量在相等的时间间隔内扫过相等的面积.

七、开普勒第三定律: 轨道周期与半长轴的关系(注释部分)

半短轴 $b$ 通过表达式与 $a$ 和 $e$ 相关: $$ \begin{equation} \label{eq:Eccentricity} b^2 = a^2 (1 - e^2). \tag{9} \end{equation} $$ 我们现在可以从上述结果推导出轨道周期. 由于位置向量在单位时间间隔内扫过的面积由 $L/m$ 给出, 因此扫过单位面积所需的时间由 $m/L$ 给出. 由于轨道周期 $T$ 是扫过椭圆整个面积 $\pi a b$ 所需的时间, 我们有 $$ \begin{equation*} T = (m / L) \pi a b. \end{equation*} $$ 代入方程 $\eqref{eq:AngularMomentum}$ 中 $L$ 的表达式, 并通过方程 $\eqref{eq:Eccentricity}$ 消去 $b$, 以及通过方程组 $\eqref{eq:Identifications}$ 中的第一个方程消去 $E$, 我们得到 $$ \begin{equation} T = \frac{2\pi\,a^{3/2}}{\sqrt{GM}}, \end{equation} $$ 这就得到了开普勒第三定律.

附录(注释部分)

在本附录中, 我们从方程 $\eqref{eq:Trajectory}$ 确定了近日点和远日点(或者更一般地说, 近地点和远地点)的距离.

在 $r = |\vec{r}|$ 达到最大值和最小值的瞬间, 速度向量 $\vec{v}$ 必须与 $\vec{r}$ 垂直. 这是因为如果 $\vec{v}$ 有任何与 $\vec{r}$ 平行或反平行的分量, 那么在那个瞬间之前或之后, 天体 $m$ 会更接近或更远离开天体 $M$, 因此它不会对应于一个最大值或最小值. 因此, $r$ 的最大值和最小值对应于 $\phi = \pm 90^\circ$ 的点, 即 $\sin^2 \phi = 1$. 将这个代入方程 $\eqref{eq:Trajectory}$ 得到一个二次方程. $$ \begin{equation} \label{eq:PeriapsisApapsisQuadratic} r^2 + \frac{GMm}{E}r - \frac{L^2}{2mE} = 0 \tag{Ap.1} \end{equation} $$ $r$ 的最大值或最小值必须满足, 它有解 $$ \begin{equation} \label{eq:PeriapsisApapsis} r = \frac{-\frac{GMm}{E} \pm \sqrt{\left ( \frac{GMm}{E} \right )^2 + 2 \frac{L^2}{m E}}}{2}. \tag{Ap.2} \end{equation} $$ 当 $E > 0$ 时, 很明显两个解都是实数, 但只有其中一个解(对应于 $+$ 符号)是正数, 那个才是唯一有效的极值. 当 $E = 0$ 时, 除以 $E$ 将是无效的, 因此我们必须首先将方程 $\eqref{eq:PeriapsisApapsisQuadratic}$ 乘以 $E$, 然后将 $E = 0$. 得到的极值是 $r_p = \frac{L^2}{2GMm^2}\; (E = 0)$. 我们通过以下论证推断, 在这两种情况下, 解对应于近日点而不是远日点: 由于天体 $m$ 必须与质量 $M$ 保持非零的最小距离(以保持非零的角动量 $L$), 必须存在一个最小值. 最大值不必存在, 因为在这些情况下, 质量 $m$ 有足够的能量逃脱 $M$ 的引力牵引并逃逸到无穷远, 正如第二节所述.

当 $E < 0$ 时, 我们已经论证了必须存在一个最小值和一个最大值. 这表明方程 $\eqref{eq:PeriapsisApapsis}$ 中的两个根都应该是实数, 即二次方程的判别式必须为正. 由于 $E < 0$, 平方根下的第二项是负数, 所以开方数小于 $-\frac{GMm}{E}$. 因此, 两个根确实是正数, 其中较小的一个($-$ 符号)对应于近日点, 较大的一个($+$ 符号)对应于远日点.

致谢

作者希望感谢班加罗尔天文学会的业余天文学家进行了有益的讨论和反馈.

原文来源

[arXiv:2111.08447]An algebra and trigonometry -based proof of Kepler's First Law

译者的话

本文有关开普勒三大定律的推导过程极其有趣, 并且几乎不使用高等数学过程, 非常推荐学习. 同时原文的 $\LaTeX$ 排版极其美观, 注释内容机器明确, 正文内容简短有力, 展现出精华部分, 非常值得大家借鉴.

摘要 本文旨在探讨生成函数在高中数学中解决数列问题的应用. 生成函数, 作为一种强大的数学工具, 允许我们将数列以形式幂级数的方式表示, 从而简化了许多复杂的数列问题. 文章首先介绍了生成函数的基本概念和定义, 包括其与序列的关系、系数的提取方法以及生成函数的加法和乘法运算规则. 随后, 通过一系列精选例题, 展示了生成函数在解决递推数列、寻找数列通项公式以及数列求和问题中的实际应用. 文章还详细讨论了如何从生成函数的封闭形式中还原出原始序列, 并提供了一些基础序列的生成函数封闭形式示例. 最后, 文章通过解决具体的数列问题, 如斐波那契数列和卡特兰数列, 进一步证明了生成函数在数学教育中的实际价值和解决问题的高效性.

关键词 生成函数; 数列; 幂级数; 泰勒展开; 组合数; 通项公式; 数列求和

0. 术语约定

• 自然数集 $\mathbb{N} = \{0,1,2,3,...\}$, $\mathbb{N}^+ = \{1,2,3,...\}$.

• 设 $\mathbb{P}$ 是某一数域, 如整数域、有理数域、实数域, $\mathbb{P}_{*} = \mathbb{P}-\{0\}$ 代表去掉 $0$ 元后的数域.

• 用 $\{a_i:i\in\mathbb{N}\}$ 来表示如下序列

$$ a_0,a_1,a_2,a_3,...,a_k,... $$

其中 $a_i$ 可以是 $\mathbb{P}$ 里的数字, 也可以是生成函数, 或者其它的东西, 总之用序列来表示一组有序对象.

• 本文中的序列均指无穷序列.
• 对于一个数字序列 $\{a_i\in\mathbb{P}\}$,若 $\exists k\in\mathbb{N}$, 使得 $\forall n > k$ 有 $a_n = 0$, 则称该序列为有限序列, 意思这个无穷序列在某一项后均为 $0$.
• 本文中的组合数不表示为 $C_{n}^{r}$, 而表示为 ${n \choose r}$, 二者定义基本相同, 但后者定义范围更广泛.

1. 生成函数定义

在这篇文章中, 首先会抛弃掉生成函数作为 “函数” 的意义, 认为它只序列的另一种表示方式, 然后再逐步证明这个 “ 序列” 具有的种种 “函数” 性质.

生成函数, 也称形式幂级数, 多项式.

设有序列 $\{a_i:a_i\in\mathbb{P}\}$. 根据序列 $\{a_i\}$, 生成函数 $f(x)$ 被定义为

$$ f(x)= a_0+a_1x+a_2x^2+a_3x^3+...+a_nx^n+... $$

也可以简记为

$$ f(x)=\sum_{i=0}^\infty a_ix^i $$

在生成函数 $f(x)$ 中, $x$ 不是未知数, 它只是一个占位符, $x^i$ 用来标记它是第几个占位符.

对于 $f(x)$ 第 $i$ 位上的 $a_i$, 我们记作 $f[i]$, $f[i]$ 也被称作 $f(x)$ 的第 $i$ 次项系数, 简称 $i$ 次项.

特别的有 $f(x)$ 的 $0$ 次项称作常数项. 于是

$$ f(x)=\sum_{i=0}^{\infty}f[i]x^i $$

$$ f(x)=f[0]+f[1]x+f[2]x^2+f[3]x^3+...+f[n]x^n+... $$

$\sum\limits^{\infty} $ 在这里的意义并不是无穷项求和, 上述定义看似是无穷项的求和, 实质上只是一个记号, 只是对序列的另一种表达方式, 因为目前已经抛弃掉生成函数作为函数的意义, 这一点尤为值得注意. 在下文, 会逐步证明 $\sum\limits^{\infty}$ 代表序列的意义与生成函数无穷项求和的意义是等价的.

为了提取序列中的某一项系数方便, 也记

$$ [x^i]f(x)=f[i] $$

这并不是多此一举, 比如提取 $1+x-2x^2+3x^3$ 的二次项系数可以简记为 $[x^2](1+x-2x^2+3x^3)$ . 对于两个生成函数 $f(x)$ 与 $g(x)$, $f(x) = g(x)$ 当且仅当 $\forall i\in\mathbb{N}$ 均满足 $f[i] = g[i]$ ,这阐明了生成函数相等的概念.

若产生生成函数 $f(x)$ 的序列 $\{f[i]\}$ 是有限序列, 则称 $f(x)$ 是有限多项式、有限幂级数, 否则称 $f(x)$ 是无穷多项式、无穷幂级数.

若 $f(x)$ 是有限多项式, 它的最高次项为 $n$, 也可以将 $f(x)$ 记为

$$ f(x)=\sum_{i=0}^nf[i]x^i $$

或者

$$ f(x)=f[0]+f[1]x+f[2]x^2+...+f[n]x^n $$

注意, 这仍然不意味着上述两种记法中, 符号 $\sum _{i = 0}^n$ 或 $+ $ 意味着有限项求和, 它们仍然只是对有限序列的另一种表达方式, 因为我们还未定义关于生成函数的加法运算.

例如:

1. 除第 $0$ 项为 $a\in\mathbb{P}$ 外的项皆为 $0$ 的序列 $\{a,0,0,0,...\}$ , 它产生的生成函数为

$$ f(x)=\sum_{i=0}^0f[i]x^i=a $$

1. 序列 $\{1,-2,1,-3,0,0,0,...\}$ 产生的生成函数为

$$ f(x)=\sum_{i=0}^3f[i]x^i=1-2x+x^2-3x^3 $$

2. 生成函数的基本运算

限于篇幅及高中范围内实用程度, 仅介绍加法运算和乘法运算.

加法运算

设 $f(x)$ 与 $g(x)$ 是两个生成函数, 它们之间进行加法运算的结果也是一个生成函数, 记作 $f(x)+g(x)$,满足

$$ [x^i](f(x)+g(x))=f[i]+g[i]\quad(i\in\mathbb{N}) $$

于是 $$ f(x)+g(x)=\sum_{i=0}^{\infty}(f[i]+g[i])x^i $$

$\mathbb{P}$ 内的数字对加法满足交换律和结合律, 因此可以直接推出生成函数对加法运算满足交换律和结合律, 也就是说

$$ f(x)+g(x)=g(x)+f(x) $$

$$ (f(x)+g(x))+h(x)=f(x)+(g(x)+h(x)) $$

根据生成函数的加法运算, 我们可以定义对生成函数的求和式.

设 $f_i(x)\left(i = 1,2,...,n\right)$ 是一组生成函数, 定义它们的有限项求和

$$ \begin{align} \sum_{i=1}^n f_i(x)&=f_1(x)+f_2(x)+f_3(x)+\cdots+f_n(x)\\ &=\sum_{j=0}^\infty\left(\sum_{i=1}^nf_i[j]\right)x^j \end{align} $$

这里仍然强调一下, 这并不是说 $\sum\limits^{\infty}$ 与 $\sum\limits^{n}$ 这两个求和可交换次序, 前者是对序列的一种表达方式, 后者是对生成函数或普通数字的有限项求和, 也就是说对生成函数求和后体现的是下面的一个新序列

$$ \left\{\left(\sum_{i=1}^nf_i[j]\right):j\in\mathbb{N}\right\} $$

乘法运算

对于两个生成函数 $f(x)$ 与 $g(x)$ ,对它们做乘法运算的结果也是一个生成函数, 记作 $f(x)\cdot g(x)$ 或简写成 $f(x)g(x)$, 满足

$$ [x^i]f(x)g(x)=\sum_{j=0}^if[j]g[i-j] $$

相当于

$$ f(x)g(x)=\sum_{i=0}^\infty\left(\sum_{j=0}^if[j]g[i-j]\right)x^i $$

与生成函数的加法运算类似, 乘法运算也满足交换律和结合律, 同时乘法运算对加法运算还满足分配律, 也就是说

$$ \begin{gathered} \begin{aligned} f(x)g(x)&=g(x)f(x)\\ (f(x)g(x))\cdot h(x)&=f(x)\cdot(g(x)h(x))\\ (f(x)+g(x))\cdot h(x)&=f(x)h(x)+g(x)h(x) \end{aligned} \end{gathered} $$

生成函数可以被粗略地看做一个有无穷项的多项式, 所以其基本运算法则均与多项式相同.

对于两个有限生成函数 $f(x),g(x)$, 设它们的最高次分别是 $n,m$, 可以证明

$$ f(x)g(x)=\sum_{i=0}^n\sum_{j=0}^mf[i]g[j]x^{ij} $$

即等式左边的生成函数等于右边一堆生成函数的求和.

这是分配律的直接推论.

3.基础序列的生成函数封闭形式举例

1. $1,1,1,1,1,\dots$ 的生成函数是 $\sum_{n = 0}^{\infty} x^n = \frac{1}{1-x} (|x| < 1)$

   证明: $(1-x) \sum_{n = 0}^{\infty} x^n = \sum_{n = 0}^{\infty}(x^n-x^{n+1}) = 1-\lim\limits_{n \to \infty}x^{n+1} = 1$

2. $1,0,1,0,1,0,\dots$ 的生成函数是 $\sum_{n = 0}^{\infty} x^{2n} = \frac{1}{1-x^2}(x^2 < 1) $

   证明: $(1-x^2) \sum_{n = 0}^{\infty} x^{2n} = 1-\lim\limits_{n \to \infty}x^{2n+2} = 1 $

3. $1,2,4,8,16,\dots$ 的生成函数是 $\sum_{n = 0}^{\infty} 2^n x^n = \sum_{n = 0}^{\infty} (2x)^n = \frac{1}{1-2x}(|x| < \frac{1}{2})$

4. $1,a,a^2,a^3,\dots$ 的生成函数是 $\sum_{n = 0}^{\infty} a^n x^n = \sum_{n = 0}^{\infty} (ax)^n = \frac{1}{1-ax}(|ax| < 1)$

5. ${n \choose 0},{n \choose 1},{n \choose 2},{n \choose 3},\dots$ 的生成函数是 $\sum_{i = 0}^{n} {n \choose i}x^i = (1+x)^n$

6. $0,1,-\frac{1}{2},\frac{1}{3},-\frac{1}{4},\dots$ 的生成函数是 $\sum_{n = 0}^{\infty}(-1)^{n}\frac{x^{n+1}}{n+1} = \ln(1+x)$

   证明: 由 $\ln (1+x)$ 的泰勒级数可得.

7. $1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\dots$ 的生成函数是 $-\frac{\ln (1-x)}{x}$

4.从封闭的幂级数形式还原原来的序列

首先知道些公式, 关于组合数的（其中 $m,n \in \N^*$）

$$ \begin{aligned} &\left(x+y\right)^{m} =\sum_{n=0}^m\binom mnx^ny^{m-n} \\ &\binom{m+n}n =\sum_{i=0}^n\binom{m+i-1}i \end{aligned} $$

第一个式子可用高中数学选择性必修三第六章中提到的二项式定理证明.

至于第二个式子的证明, 其实拿杨辉三角一直往上拆直到拆光就行了.

我们定义牛顿二项式系数如下:

$$ {r\choose n}= \begin{cases} 0 &(n<0)\\ 1 &(n=0)\\ \frac{r(r-1)\cdots(r-n+1)}{n!} &(n>0) \end{cases} $$

虽然这和组合数定义很像, 但其中 $n \in \Z,r \in \R$, 所以其没有组合意义. 后面出现的类似式子在没有强调时都代表牛顿二项式系数.

类似的我们可以有牛顿二项式定理:

$$ \left(x+y\right)^{m} =\sum_{n=0}^{\infty} \binom mnx^ny^{m-n} $$

其中 $m \in \R$. 证明方式: 将左式泰勒展开.

同时给出如下常用结论:

1. $\large {-m \choose n} = (-1)^n {m+n-1 \choose n}$, 其中 $m$ 为正整数, $n$ 为整数

2. 令 $m$ 为正整数, 则有

   $$ \begin{aligned} &(1+x)^m =\sum_{n=0}^\infty(-1)^n\binom{m+n-1}nx^n \\ &(1-x)^m =\sum_{n=0}^\infty\binom{m+n-1}nx^n \end{aligned} $$

3. 令 $m = \frac{1}{2}$, 则有

   $$ (1+x)^{\frac12}=1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{2^{2n-1}n}\binom{2n-2}{n-1}x^n $$

我们从斐波那契数列的生成函数推导通项公式为例讲解.

斐波那契通项公式

给定斐波那契数列递推式

$$ \left.\left\{\begin{aligned}&f_0=f_1=1\\&f_n=f_{n-1}+f_{n-2}\quad(n\geq2)\end{aligned}\right.\right. $$

求其第 $n$ 项的通项公式.

设斐波那契数列 $\{f_n\}$ 的普通生成函数为 $G(x) = \sum_n^\infty f_nx^n$ .

则有:

$$ \begin{aligned} G(x)& =1+x+\sum_{n=2}^\infty(f_{n-1}+f_{n-2})x^n \\ &=1+x+x\sum_{n=2}^\infty f_{n-1}x^{n-1}+x^2\sum_{n=2}^\infty f_{n-2}x^{n-2} \\ &=1+x+x\sum_{n=1}^\infty f_nx^n+x^2\sum_{n=0}^\infty f_nx^n \\ &=1+x+x(G(x)-1)+x^2G(x) \\ &=1+(x^2+x)G(x) \end{aligned} $$

解得:

$$ G(x)=-\frac{1}{x^2+x-1} $$

我们的目的是将其拆成

$$ C_1(x_1+y_1)^{\alpha_1}+C_2(x_2+y_2)^{\alpha_2}+C_3(x_3+y_3)^{\alpha_3}+\cdots $$

才能使用二项式定理, 因此我们对 $x^2+x-1$ 因式分解: $x^2+x-1 = (x-\frac{-1+\sqrt{5}}{2})(x-\frac{-1-\sqrt{5}}{2})$

因此

$$ G(x)=\frac{1}{\sqrt{5}}(\frac{-1}{x-\frac{-1+\sqrt{5}}{2}}+\frac{1}{x-\frac{-1-\sqrt{5}}{2}}) $$

对 $\large -(x-\frac{-1+\sqrt{5}}{2})^{-1}$ 和 $\large (x-\frac{-1-\sqrt{5}}{2})^{-1}$ 分别代入牛顿二项式定理（常数用 $p$ 代替）可得

$$ (x-p)^{-1}=\sum_{n=0}^{\infty} \binom {-1} {n} x^n (-p)^{-1-n}=-\sum_{n=0}^{\infty} \frac{x^n}{p^{n+1}} $$

因而

$$ G(x)=\sum_{n=0}^{\infty}\frac{1}{\sqrt{5}}\left((\frac{-1+\sqrt{5}}{2})^{-n-1}-(\frac{-1-\sqrt{5}}{2})^{-n-1} \right)x^n $$

因此斐波那契数列通项公式则为:

$$ \begin{align} f_n&=\frac{1}{\sqrt{5}}\left((\frac{-1+\sqrt{5}}{2})^{-n-1}-(\frac{-1-\sqrt{5}}{2})^{-n-1} \right)\\ &=\frac{1}{\sqrt{5}}\left((\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1} \right) \end{align} $$

卡特兰数通项公式

给定卡特兰数数列递推式 (下标从 1 开始)

$$ \left.\left\{\begin{aligned}h_1&=1\\h_n&=\sum_{k=1}^{n-1}h_kh_{n-k}&(n\geq2)\end{aligned}\right.\right. $$

求其第 $n$ 项的通项公式.

设 $\{h_n\}$ 的生成函数为 $H(x) = \sum\limits_{i = 1}^\infty h_nx^n$.

将其两边平方得

$$ \begin{aligned} H^{2}(x)& =\left(\sum_{i=1}^\infty h_ix_i\right)\left(\sum_{j=1}^\infty h_jx_j\right) \\ &=\sum_{n=2}^\infty x^n\sum_{k=1}^{n-1}h_kh_{n-k} \\ &=\sum_{n=2}^\infty h_nx^n \\ &=H(x)-x \end{aligned} $$

解上式中推出的关于 $H(x)$ 的方程得

$$ \begin{aligned}H_1(x)&=\frac{1+(1-4x)^{\frac12}}2\\H_2(x)&=\frac{1-(1-4x)^{\frac12}}2\end{aligned} $$

由于 $H(0) = 0$, 所以 $H_1(x)$ 舍去, 取 $H(x) = H_2(x)$.

根据常用结论 3 $$ (1+x)^{\frac12}=1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{2^{2n-1}n}\binom{2n-2}{n-1}x^n $$

可知

$$ (1-4x)^{\frac12}=1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{2^{2n-1}n}\binom{2n-2}{n-1}(-4x)^n=1-\sum_{n=1}^{\infty}\frac2n\binom{2n-2}{n-1}x^n $$

将上式带入 $H_2(x)$

$$ H(x)=H_2(x)=\sum_{n=1}^\infty\frac1n\binom{2n-2}{n-1}x^n $$

故

$$ h_n=\frac1n\binom{2n-2}{n-1} $$

所以, 下标从 $0$ 开始的卡特兰数通项公式即为

$$ h_n=\frac{1}{n+1} {2n \choose n} $$

总结: 使用生成函数求解给定递推式序列的通项式的一般方法:

1. 设出 $\{a_n\}$ 的生成函数 $G(x)$ .
2. 利用递推方程的依赖关系, 导出关于生成函数 $G(x)$ 的方程.
3. 求解方程, 得到关于 $G(x)$ 的函数表达式.
4. 将 $G(x)$ 展开成属级数的形式, $x^n$ 项的系数即为 $a_n$ .

5.题目探究

求数列通项公式

1. （高考数学压轴题P4例1(2)）设 $b > 0$, 数列 $\{a_n \}$ 满足 $a_1 = b,a_n = \frac{nba_{n-1}}{a_{n-1}+n-1}( n \ge 2)$, 求数列 $\{a_n \}$ 的通项公式.

   解: 对 $a_n = \frac{nba_{n-1}}{a_{n-1}+n-1}$ 进行变换可得

   $$ a_n(a_{n-1}+n-1) =nba_{n-1}\\ b\frac{n}{a_n}=1+\frac{n-1}{a_{n-1}} $$

   设 $\Large F(x) = \sum\limits_{n = 1}^{\infty} \frac{n}{a_n} x^n$, 则

   $$ \begin{align} F(x)&=\sum\limits_{n=1}^{\infty} \frac{n}{a_n} x^n\\ &=\frac{x}{b} + \frac{1}{b} \sum\limits_{n=2}^{\infty} (1+\frac{n-1}{a_{n-1}}) x^n\\ &=\frac{x}{b} + \frac{x}{b} \sum\limits_{n=1}^{\infty} (1+\frac{n}{a_{n}}) x^n\\ &=\frac{x}{b}+\frac{x^2}{b(1-x)}+\frac{x}{b} F(x) \end{align} $$

   $$ \begin{align} (\frac{b}{x} -1)F(x)&=\frac{1}{1-x}\\ F(x)&=\frac{x}{(1-x)(b-x)}\\ &=\frac{\frac{1}{1-b}}{1-x}-\frac{\frac{b}{1-b}}{b-x} \end{align} $$

   当 $b = 1$ 时, 可得 $F(x) = \frac{x}{(1-x)^2}$. 因此

   $$ \begin{align} F(x)&=x\cdot (x-1)^{-2}\\ &=x\cdot\sum_{n=0}^{\infty} {-2 \choose n} x^n (-1)^{-2-n}\\ &=x\cdot \sum_{n=0}^{\infty} (-1)^n (n+1)x^n(-1)^{-2-n}\\ &=\sum_{n=1}^{\infty}n x^n\\ \end{align} $$

   也即 $\frac{n}{a_n} = n \implies a_n = 1$.

   当 $b \neq 1$ 时, 可得

   $$ \begin{align} F(x)&=\frac{1}{1-b}\sum_{n=0}^{\infty} x^n-\frac{b}{1-b}\sum_{n=0}^{\infty}\frac{x^n}{b^{n+1}}\\ &=\sum_{n=0}^{\infty} \left(\frac{1}{1-b}-\frac{1}{(1-b)b^n} \right)x^n\\ &=\sum_{n=1}^{\infty} \left(\frac{b^n-1}{(1-b)b^n} \right)x^n \end{align} $$

   因此

   $$ \frac{n}{a_n}=\frac{b^n-1}{(1-b)b^n}\\ a_n=\frac{nb^n(1-b)}{b^n-1} $$

2. （高考数学压轴题P5例2(1)）数列 $\{a_n \}$ 满足 $a_1 = 1,a_2 = 11,a_{n+2} = 2a_{n+1}+3a_n+4 (n \in \N^*)$, 求数列 $\{a_n \}$ 的通项公式.

   解: 设 $\Large F(x) = \sum\limits_{n = 1}^{\infty} a_n x^n$, 则

   $$ \begin{align} F(x)&=\sum\limits_{n=1}^{\infty} a_n x^n\\ &=x+11x^2+ \sum\limits_{n=3}^{\infty} (2a_{n-1}+3a_{n-2}+4) x^n\\ &=x+11x^2+2x\sum_{n=2}^{\infty}a_nx^n+3x^2\sum_{n=1}^{\infty}a_nx^n+4x^3\sum_{n=0}^{\infty}x^n\\ &=x+11x^2+2x(F(x)-x)+3x^2F(x)+\frac{4x^3}{1-x}\\ &=x+9x^2+(3x^2+2x)F(x)+\frac{4x^3}{1-x} \end{align} $$

   因此 $$ (3x^2+2x-1)F(x)=\frac{x}{1-x}(5x^2-8x-1) $$

   设 $t_1,t_2,t_3 \in \R$, 则

   $$ \left\{ \begin{align} F(x)=x\left(\frac{t_1}{1-x}+\frac{t_2}{3x-1}+\frac{t_3}{x+1} \right)\\ t_1(3x-1)(x+1)+t_2(1-x)(x+1)+t_3(1-x)(3x-1)=5x^2-8x-1 \end{align} \right. $$

   解得

   $$ t_1=-1,t_2=-\frac{7}{2} ,t_3=-\frac{3}{2} $$

   因此

   $$ \begin{align} F(x)&=x\sum_{n=0}^{\infty}\left(-1+ \frac{7}{2}\cdot 3^n-\frac{3}{2}\cdot (-1)^n \right)x^n\\ &=\sum_{n=1}^{\infty}\left(-1+ \frac{7}{6}\cdot 3^n+\frac{3}{2}\cdot (-1)^n \right)x^n \end{align} $$

   从而得 $a_n = -1+ \frac{7}{6}\cdot 3^n+\frac{3}{2}\cdot (-1)^n$.

数列求和

1. 求 $\Large \sum\limits_{n = 0}^{\infty} \frac{1}{n+1}(\frac{1}{2})^n$

   解: 我们发现可以将上式写成 $\Large \sum\limits_{n = 0}^{\infty} \frac{1}{n+1}x^n$, 其中 $x = \frac{1}{2}$.

   因此我们求出 $\{\frac{1}{n+1} \}$ 的生成函数 $-\frac{\ln(1-x)}{x}$, 并将 $x = \frac{1}{2}$ 代入可得答案 $2\ln 2$.

2. 设数列 $\{a_n \}$ 满足 $a_0 = \frac{1}{2} ,a_1 = \frac{3}{4} b$, $a_n = \frac{b \cdot a_{n-1}}{2}(n \ge 2)$, 其中 $b$ 为正实数. 当满足: 对任意正整数 $n$ 都有 $\displaystyle \sum_{k = 0}^{n}a_k < 2^b$ 时, 求 $b$ 的取值范围.

   解: 由题可得 $a_n = \frac{3}{4} b^n \cdot 2^{1-n} (n\ge 1)$.

   因此我们只需求出 $\{\frac{1}{2} ,\frac{3}{4} ,\frac{3}{8},\frac{3}{16},\cdots \}$ 的生成函数, 即

   $$ \displaystyle F(x)=\frac{1}{2} +\frac{3}{2} \sum_{n=1}^{\infty}\frac{1}{2^n}x^n=\frac{1}{2} +\frac{3}{2} (\frac{2}{2-x}-1)=\frac{1+x}{2-x} $$

   将 $x = b$ 代入即得 $F(b) = \frac{1+b}{2-b}$. 由于数列 $\{a_n \}$ 在 $b\ge 2$ 时单调不递减, 因此总存在 $n$ 使得 $b > 2$ 时 $\displaystyle \sum_{k = 0}^{n}a_k > 2^b $.

   当 $0 < b < 2$ 时, $\{a_n\}$ 单调递减, 因此只需解 $\frac{1+b}{2-b} \le 2^b$.

   设 $f(x) = 2^x-\frac{1+x}{2-x}$, 则 $f'(x) = 2^x\ln 2-\frac{3}{(2-x)^2}$.

   要证 $2^x\ln 2 < \frac{3}{(2-x)^2}$, 则需证 $2^x(2-x)^2 < \frac{3}{\ln 2}$.

   对左式求导可得 $2^x\ln 2(2-x)^2-2\cdot 2^x(2-x)$. 当其等于 $0$ 时, $x = 2$ 或 $x = 2-\frac{2}{\ln 2}$.

   当 $x \in (2-\frac{2}{\ln 2},2)$ 时, $2^x\ln 2(2-x)^2-2\cdot 2^x(2-x) < 0$.

   因此 $f'(x) = 2^x\ln 2-\frac{3}{(2-x)^2} < 0 (0 < x < 2)$.

   因此 $f(x)$ 在 $(0,2)$ 单调递减.

   又由 $f(1) = 0$ 可得当 $b \in (0,1]$ 时 $\frac{1+b}{2-b} \le 2^b$.

3. 设数列 $\{a_n\}$ 满足 $a_n = n^2$, 数列 $\{b_n \}$ 满足 $b_n = \frac{1}{2^n}$. 设数列 $\{c_n\}$ 满足 $\displaystyle c_n = \sum_{k = 0}^{n}a_kb_{n-k}$. 求证: 对任意正整数 $n$ 都有 $\displaystyle \sum_{k = 0}^n b_kc_k < 8$.

   解: 我们分别求出 $\{a_n\},\{b_n \}$ 的生成函数为 $F(x) = \frac{x(x+1)}{(1-x)^3},G(x) = \frac{2}{2-x}$.

   则 $\{c_n \}$ 的生成函数 $H(x) = F(x)G(x) = \frac{2x(x+1)}{(1-x)^3(2-x)}$.

   将 $x = \frac{1}{2}$ 代入可得 $\displaystyle \sum_{k = 0}^{\infty} b_kc_k = 8$. 由 $\{b_nc_n\}$ 为递增数列可得 $\displaystyle \sum_{k = 0}^n b_kc_k < 8$.

6. 练习题

1. 给 $n_1$ 个 $1$, $n_2$ 个 $2$, $n_3$ 个 $5$, 问它们不能组成的最小正整数是多少？(建立生成函数, 并指出答案对应的是生成函数中哪一项的指数或系数)

2. 小光得到了 $3$ 罐糖果. 不同的糖果罐, 糖果的种类不同（即同一个糖果罐里的糖果种类是相同的, 不同的糖果罐里的糖果的种类是不同的）. 三个糖果罐里分别有 24 3 25 个糖果. 小光决定吃掉一些糖果, 他想吃掉至少 $5$ 个糖果, 但不超过 $14$ 个.

   小光无法确定吃多少个糖果和每种糖果各吃几个. 有多少种方法可以做这件事呢？(提示：生成函数建立正确后, 本题计算并不复杂)

参考文献

1. Lando, S.K. (2003). Lectures on Generating Functions.
2. Wilf, H.S. (2005). Generating Functionology: Third Edition (3rd ed.). A K Peters/CRC Press. https://doi.org/10.1201/b10576
3. 曹永生 (2023). 高考数学压轴题破解策略
4. 张新华 (2023). 信息学竞赛宝典

摘要 本文从与 Bertrand 假设有关的数论函数出发, 给出一些定理及引理, 从而证明了 Bertrand 假设在 $n$ 较大时成立. 而后通过寻找特殊数, 得出 Bertrand 假设在 $n \ge 4000$ 时, Bertrand 假设成立. 同时又通过枚举 $4000$ 以内的特殊质数数列, 证明了 Bertrand 假设成立.

关键词 Bertrand 假设; 数论函数; 素数

注意, 以下出现的一切变量 $p$ 都为素数.

Bertrand 假设断言, 对于任意正整数 $n \ge 2$, 存在素数 $p$ 满足 $n \le p < 2n$, 这是素数分布中比较初等的一个结果, 由 Joseph Bertrand 在 1845 年提出, Pafnuty Chebyshev 在 1850 年给出了该假设的第一个严格证明, 但未使用初等方法. 第一个初等证明是由 Ramanujan 提出的, 后来在 1932 年由 19 岁的 Erdős 改进. 本文对前人的工作进行了总结与汇总.

定理 1. 对于任意正整数 $n \ge 2$, 存在素数 $p$ 满足 $n \le p < 2n$.

1. 数论函数简介

定义 1.1 设 Mangoldt 函数如下 $$ \Lambda(n)= \begin{cases} \ln p &n=p^k(p \text{为质数})\\ 0 &\text{otherwise} \end{cases} \tag{1} $$

定义 1.2 设莫比乌斯函数如下 $$ \mu(n)= \begin{cases} (-1)^k &\text{其中} k \text{为} n \text{的质因子个数(可重复)}\\ 0 &\exists p \in \text{质数},p^2 |n \end{cases} \tag{2} $$

定理 1.3 因此可以通过定义得到如下式子

$$ \sum_{d|n}\mu(\frac{n}{d})\ln d=\Lambda(n) \tag{3} $$

$$ \sum_{d|n} \Lambda(d)=\ln n\tag{4} $$

$$ \sum_{d|n} \mu(d)\ln d=-\Lambda(n)\tag{5} $$

$$ \sum_{d|n}\mu(\frac{n}{d})\Lambda(d)=-\mu(n)\ln n\tag{6} $$

定义 1.4 对前缀和 Mangoldt 函数有如下定义

$$ \psi(x)=\sum_{n\le x}\Lambda(n)\tag{7} $$

Von Mangoldt 本人证明了

$$ \psi(x) \sim x\tag{8} $$

下式与黎曼猜想等价

$$ \psi(x)=x+O(\sqrt{x}\ln^2x)\tag{9} $$

这一式子超出讨论范围, 不做证明.

定义 1.5 设 $T(x)=\ln \lfloor x\rfloor!$.

2. $T(x)$ 函数估阶

定理 2.1 Vardi (1991, p. 155) 证明了一个有趣的式子

$$ T(x)=\psi(x)+\psi(\frac{1}{2}x)+\psi(\frac{1}{3}x)+\dots\tag{10} $$

证明：运用 Von Mangoldt 函数本身的性质可得(可由 $(4)$ 式推出)

$$ T(x)=\sum_{n\le x}\Lambda(n)\lfloor \frac{x}{n} \rfloor\tag{11} $$

运用取整函数的性质可得

$$ T(x)-2T(\frac{x}{2})\ge \psi(x)-\psi(\frac{x}{2})\tag{12} $$

我们记 $n=\lfloor x\rfloor$, 则有

$$ \begin{align} \ln n!&=\sum_{i=1}^n\ln i=\sum_{i=1}^n\ln i(i-(i-1))\\ &=n\ln n+\sum_{i=1}^{n-1}i\ln i -\sum_{i=2}^n (i-1)\ln i\\ &=n\ln n-\sum_{i=1}^{n-1}i(\ln (i+1)-\ln i)\\ &=n\ln n-\sum_{i=1}^{n-1}i\int_i^{i+1}\frac{1}{t}\mathrm{d}t\\ &=n\ln n-\int_1^n \lfloor t\rfloor \frac{1}{t}\mathrm{d}t\\ &=n\ln n-\int_1^n (1-\frac{t-\lfloor t\rfloor}{t})\mathrm{d}t\\ &=n\ln n-\int_0^n1\mathrm{d}t+O(\ln n)\\ &=n\ln n-n+O(\ln n) \end{align} $$

因此

$$ T(x)=x\ln x-x+O(\ln x)\tag{13} $$

其中 $O$ 记号为渐近符号.

因此我们有

$$ T(x)-2T(\frac{x}{2})=x\ln 2 +O(\ln x) \tag{14} $$

由 $(12)(14)$ 可得

$$ \psi(x)-\psi(\frac{x}{2})\le x\ln 2+O(\ln x)\\ \psi(x)\le \psi(\frac{x}{2})+x\ln 2+O(\ln x) \tag{15} $$

迭代运用 $(15)$ 可得

$$ \large \begin{align} \psi(x)&=\sum_{k=1}^{log_2 x}[\psi(\frac{x}{2^{k-1}})-\psi(\frac{x}{2^k})]\\ &\le \sum_{r\ge 1}\frac{x\ln 2}{2^{k-1}}+O(\ln^2 x)\\ &=2x\ln 2+O(\ln^2x) \end{align} $$

因此

$$ \psi(x)\le 2x\ln 2+O(\ln^2 x)\tag{16} $$

通过交换求和次序可得

$$ \begin{align} T(x)&=\sum_{n\le x}\Lambda(n)\lfloor \frac{x}{n} \rfloor\\ &=\sum_{n\le x}\Lambda(n)\sum_{q\le x/n}1\\ &=\sum_{qn\le x}\Lambda(n)\\ &=\sum_{q\le x}\sum_{n\le x/q}\Lambda(n)\\ &=\sum_{q\le x}\psi(\frac{x}{q}) \end{align} $$

$ \square$

3. 定理 1 的粗略证明

将上式代入 $(14)$ 中, 就有

$$ \psi(x)-\psi(\frac{x}{2})+\psi(\frac{x}{3})-\psi(\frac{x}{4})+\cdots=x\ln 2+O(\ln x) $$

因为 $\psi(x)$ 单调递增, 所以左侧的交错和必然不超过 $\psi(x)-\psi(\frac{x}{2})+\psi(\frac{x}{3})$, 那么

$$ \psi(x)-\psi(\frac{x}{2})\ge x\ln 2-\psi(\frac{x}{3})+O(\ln x)\tag{17} $$

结合 $(16)$ 我们可以得到

$$ \psi(x)-\psi(\frac{x}{2})\ge \frac{x}{3}\ln 2+O(\ln^2 x)\tag{18} $$

由于 $\Lambda(n)$ 仅在 $n=p^k$ 时非零, 所以这个不等式表明对于足够大的 $x$, $(\frac{x}{2},x]$ 中总有素数的幂次.

接下来对 $(16)$ 进行调整来证明 Bertrand 假设.

事实上如果定义

$$ \vartheta(x)=\sum_{p\le x}\ln p $$

则有

$$ \large \begin{align} \psi(x)&=\sum_{k\le \log_2 x}\sum_{p\le x^{1/k}}\ln p\\ &=\sum_{p\le x}\ln p+\sum_{p\le \sqrt{x}} \ln p+\sum_{k=3}^{\log_2x}\sum_{p\le x^{1/k}}\ln p \\ &=\vartheta(x)+\vartheta(\sqrt{x})+\sum_{k=3}^{\log_2x} \vartheta(x^{1/k}) \end{align} $$

再根据 $\vartheta(x)\le \psi(x)$ 和 $\vartheta(x)\sim x$ 且 $\vartheta(x)\le x$, 有如下式子

$$ \begin{align} \psi(x)&=\vartheta(x)+O(\sum_{k=2}^{\log_2x}x^\frac{1}{k})\\ &=\vartheta(x)+O(\sqrt{x}) \end{align} $$

因此得到联系 $\vartheta(x)$ 和 $\psi(x)$ 的渐近公式

$$ \psi(x)=\vartheta(x)+O(\sqrt{x})\tag{19} $$

将 $(19)$ 代入 $(18)$ 中, 可得

$$ \sum_{\frac{x}{2}< p\le x}\ln p \ge \frac{x}{3}\ln x+O(\sqrt{x})\tag{20} $$

而这个公式预示着随着 $x$ 的增加, $(\frac{x}{2},x]$ 的素数个数也会跟着增加, 从而证明 Bertrand 假设在 $x$ 足够大时成立.

而当 $x$ 较小时, 可以通过枚举的方式易得出 Bertrand 假设是正确的.

4. 定理 1 的初等证明

我们把目光先放到 $\vartheta(n)$ 身上. 接下来希望证明假设 $\vartheta(n)< (n-1)\ln 4$. 也即

$$ \prod_{p\le n}p < 4^{n-1} \tag{21} $$

(其实现在必然需要上文提到的 $\psi(x),\vartheta(x),\Lambda(x)$ 中至少一个的上界, 而 $\vartheta(x)$ 是形式最简便的, 因此对它下手. 至于这个形式则是一个可以通过初等形式得到证明的)

运用归纳法, 发现 $n=2$ 时假设显然成立. 而 $\vartheta(2m+2)=\vartheta(2m+1)$, 因此仅对 $n=2m+1$ 的情况进行证明.

假设 $n\le 2m$ 时 $\vartheta(n) < (n-1)\ln 4$ 成立, 我们设 $n=2m+1$, 则我们有

$$ \begin{align} \vartheta(n)&=\vartheta(2m+1)\\ &=\vartheta(m+1)+\sum_{m+1< p \le 2m+1}\ln p\\ &< m \ln 4+\sum_{m+1 < p \le 2m+1}\ln p\\ &\le m\ln 4+\ln {2m+1\choose m+1}\\ &\le m\ln 4 +\ln \frac{1}{2}\sum_{i=0}^{2m+1}{2m+1\choose i} \\ &= m\ln 4 + \ln \frac{1}{2}\cdot 2^{2m+1} \\ &= 2m\ln 4 \end{align} $$

因此 $\vartheta(n)<(n-1)\ln 4$, 原假设成立.

定理 4.1(Lengendre 定理) 即 $n!$ 中素数 $p$ 的次数恰好为 $\sum\limits_{k\ge 1}\lfloor \frac{n}{p^k} \rfloor$.

证明：$n!=1\cdot 2\cdot 3\cdots \cdot n$ 中恰有 $\lfloor \frac{n}{p} \rfloor$ 项被 $p$ 整除, 恰有 $\lfloor \frac{n}{p^2} \rfloor$ 被 $p^2$ 整除, 依此类推. $\square$

根据该定理, ${2n\choose n}=\frac{(2n)!}{(n!)^2}$ 中素因子 $p$ 的次数恰好为

$$ \sum\limits_{k\ge 1}(\lfloor \frac{2n}{p^k} \rfloor-2\lfloor \frac{n}{p^k} \rfloor)\tag{22} $$

其中

$$ \lfloor \frac{2n}{p^k} \rfloor-2\lfloor \frac{n}{p^k} \rfloor<\frac{2n}{p^k}-2(\frac{n}{p^k}-1)=2 $$

因此和式中的每一项至多为 $1$. 所以

$$ \sum\limits_{k\ge 1}(\lfloor \frac{2n}{p^k} \rfloor-2\lfloor \frac{n}{p^k} \rfloor)\le \max(r:p^r\le 2n)\tag{23} $$

因此, 当 $p>\sqrt{2n}$ 时, $p$ 在 $2n\choose n$ 中的次数最多为 $1$.

当 $n < p \le 2n$ 时, $p$ 在 $2n\choose n$ 中的次数正好为 $1$.

当 $3p>2n$ 且 $n\ge 3$ 时, $p$ 和 $2p$ 是仅有的两个出现在 $\frac{(2n)!}{(n!)^2}$ 的分子中的 $p$ 的倍数, 而分母中同时也恰有 $p$ 的二重因子. 因此 $\frac{2}{3}n < p\le n$ 的素数 $p$ 不会整除 $2n\choose n$.

所以当 $p\le \sqrt{2n}$ 时, $2n\choose n$ 中有 $p$ 的多重因子, 当 $\sqrt{2n} < p \le \frac{2}{3} n$ 时, $2n \choose n$ 中 $p$ 的次数最多为 $1$ , 当 $ n < p\le 2n$ 时, $2n\choose n$ 中 $p$ 的次数恰好为 $1$.

利用对二项式系数的估计与 $(23)$, 有

$$ \frac{4^n}{2n}\le {2n\choose n}\le \prod_{p\le \sqrt{2n}}2n\cdot \prod_{\sqrt{2n} < p\le\frac{2}{3}n}p\cdot \prod_{ n < p\le 2n}p $$

由于满足 $p\le \sqrt{2n}$ 的素数不超过 $\sqrt{2n}$ 个, 从上式与 $(21)$ 可以得到

$$ 4^n < (2n)^{\sqrt{2n}+1}\cdot 4^{\frac{2}{3}n-1}\prod_{n < p\le 2n} p\tag{24} $$

假设 $(n,2n]$ 中不存在质数, 那么

$$ 4^n<(2n)^{1+\sqrt{2n}}4^{\frac{2}{3}n-1}\\ 4^{\frac{1}{3}n+1}<(2n)^{1+\sqrt{2n}} $$

利用 $x+1 < 2^x (x\ge 2)$ 可得

$$ \begin{align} 2n=(\sqrt[6]{2n})^6<(\sqrt[6]{2n}+1)^6 < 2^{6\sqrt[6]{2n}} \end{align} $$

也即

$$ 2^{2n+6}<(2n)^{3(1+\sqrt{2n})} < 2^{18\sqrt[6]{2n}(1+\sqrt{2n})} < 2^{20(2n)^\frac{2}{3}} $$

这要求 $2n+6 < 20(2n)^\frac{2}{3}$, 则 $n < 4000$.

当 $n < 4000$ 时, 运用枚举可得 $(n,2n]$ 至少存在一个质数. 枚举如下：

$$ 2,3,5,7,13,23,43,83,163,317,631,1259,2503,4001 $$

上面的每个质数都小于前一个的两倍, 那么对于 $n < 4000$, $(n,2n]$ 必然包括上面 $14$ 个质数中的一个.

5. 总结

这篇论文通过对前人证明 Bertrand 假设的方式进行总结, 呈现了两种较为简洁的证明方式.

同时, Bertrand 假设又与 Legendre 猜想相似. Legendre 猜想表述为：对于任意正整数 $n$, 存在 $p$ 满足 $n^2 < p \le (n+1)^2$. 不过这个猜想到目前为止还未被证明.

在此基础上, Bertrand 假设还可以改进为：对于足够大的正整数 $N$, 对于任意 $n \ge N$, 存在素数 $p$ 满足 $n \le p < n+O(n^{\theta})$. 目前为止, 该猜想的最好结果是 $\theta=\frac{6}{11}+\epsilon$, 于 1992 年被证明.

参考文献

1. J. Bertrand, M´emoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu’elle renferme, Journal de l’Ecole Royale Polytechnique Cahier 30, 18 (1845), 123–140.
2. [德]Martin Aigner,Günter M. Ziegler.数学天书中的证明[M].冯荣权,宋春伟,宋传明译.北京:高等教育出版社,2009:7-10.
3. P. Erdős: Beweis eines Satzes von Tschebyschef, Acta Sci. Math.(Szeged)5(1930-32),194-198.
4. G. H. Hardy & E. M. Wright: An Introduction to the Theory of Numbers,fifth edition, Oxford University Press 1979.