这篇博客用于记录一些杂七杂八的数学题目以及相关的知识。
设\(a_n = \displaystyle (1+\frac{1}{n})^n\)，求证：\(\forall n \in \text{N}^+, a_{n+1}>a_n\)
解法一
\(a_n=\displaystyle \prod_{i=1}^{n} (1 +\frac{1}{n})=\prod_{i=1}^{n} (1 +\frac{1}{n})\cdot 1 \leq [\frac{\displaystyle \sum_{i=1}^{n}(1+\frac{1}{n})+1}{n+1}]^{n+1}=(1+\frac{1}{n+1})^{n+1}=a_{n+1}\)
上式中的取等条件为\(\displaystyle \frac{1}{n}+1=1\)，这显然是不可能成立的，故\(a_{n+1} > a_{n}\)。
这个解法使用了均值不等式，即\(\forall a_1, a_2,\dots,a_n \in \text{R}\)，\(H_n \leq G_n \leq A_n\leq Q_n\)，其中四个均值分别为调和平均数、几何平均数、算数平均数和平方平均数，不等式取等条件都是\(\forall i,j\in\{1,2,\dots,n\},a_i=a_j\)。上面的证明使用到了\(G_n\leq A_n\)的变形，即\(\displaystyle \prod_{i=1}^{n}a_i \leq (\frac{\displaystyle \sum_{i=1}^{n}a_i}{n})^n\)。
解法二
\(\displaystyle \frac{a_{n+1}}{a_n} = [1-\frac{1}{(n+1)^2}]^n \cdot \frac{n+2}{n+1} \geq [1-\frac{n}{(n+1)^2}] \cdot \frac{n+2}{n+1} > (1-\frac{1}{n+2}) \cdot \frac{n+2}{n+1}=1\)
以上证明使用了伯努利不等式，即\(\forall x > -1\)：
- \(n\geq1 \Rightarrow (1+x)^n\geq1+nx\)；
- \(n\in[0,1] \Rightarrow(1+x)^n\leq1+nx\)。
此外，\(\displaystyle \frac{n}{(n+1)^2}=\frac{1}{n+\displaystyle\frac{1}{n}+2}<\frac{1}{n+2}\)。
解法三
设\(y=e^{\displaystyle x\ln(1+\frac{1}{x})}, x\in \text{R}^+\)，则\(f'(x)=[\displaystyle\ln(1+\frac{1}{x})-\frac{1}{x+1}]f(x)\)。
设\(g(x)=\ln(1+x)-\displaystyle\frac{x}{1+x}\)，则\(g'(x)=\displaystyle\frac{x}{1+x} > 0\)，那么\(f'(x)>0\)，那么\(f(x)\)在\(\text{R}^+\)上单调递增，原命题显然。
删数问题
题目描述
已知有一数组，其元素为\(1,2,3,\dots,100\)共\(100\)个数，现随机删除\(2\)个数，并将其余\(98\)个数乱序存于另一数组，试问如何求出这\(2\)个数？
求解思路
对于删除\(1\)个数的情况，可以利用\(100\)个数的总和为\(5050\)的条件，遍历剩余的\(99\)个数并得到总和\(B_1\)，则被删去的数就是\((5050 -B_1)\)。
事实上，不难发现原来\(100\)个数的乘积也是常数\(100!\)，那么可以得到剩下\(98\)个数的和、乘积，即可得到被删除的\(2\)个数的和、乘积，逆用韦达定理即可构造关于这\(2\)个数的一元二次方程，求解这个方程，得到的两根一定是被删去的数。
推广
那么，以上求解方程的思想是否可以推广到删除超过\(2\)个数的情况呢？我经过思考后认为可以。
设被删除的数为\(\{b_1,b_2,\dots,b_t\}\)共\(t\)个，可以通过构造一元\(t\)次方程求解被删除的数，其中\(1\leq t \leq99\)。
首先可以通过剩余\((100-t)\)个数得到\(\displaystyle \sum_{i=1}^tb_i\)和\(\displaystyle \prod_{i=1}^tb_i\)，不妨分别记之为\(B_1\)和\(B_t\)。
考虑\(\displaystyle (\sum_{i=1}^{100}i)^2 = 5050^2\)，那么：
\[\begin{aligned} 5050^2 & =\displaystyle (\sum_{i=1}^{100}i)^2 \\ &= ((\sum_{i=1}^tb_i)+(5050-\sum_{i=1}^tb_i))^2\\ & = \displaystyle (\sum_{i=1}^tb_i)^2 + (5050-\sum_{i=1}^tb_i)^2+2(\sum_{i=1}^tb_i)(5050-\sum_{i=1}^tb_i) \\ & = B_1^2+(5050-B_1)^2+10100B_1+2\displaystyle (\sum_{i=1}^tb_i)(\sum_{i=1}^tb_i) \\ &= B_1^2+(5050-B_1)^2+10100B_1+2\displaystyle (\sum_{i=1}^tb_i^2 + \sum_{1\leq i < j \leq t} b_i b_j)\end{aligned}\]
不妨记\(\displaystyle \sum_{1\leq i < j \leq t} b_i b_j = B_2\)。由于\(100\)个数的平方和是一定的，那么可以得到\(\displaystyle \sum_{i=1}^tb_i^2\)也是常数。恒等式左侧中仅有\(B_2\)是未知数，而右侧为常数，那么可以求解得到\(B_2\)。
现在不妨观察已经得到的\(3\)个常系数，这\(3\)个系数与\(\{b_1,b_2,\dots,b_t\}\)之间的关系为：
\[\begin{cases} \displaystyle \sum_{i=1}^{t}b_i=B_1\\ \displaystyle \sum_{1\leq i < j \leq t} b_i b_j = B_2\\b_1b_2\cdots b_t = B_t\\ \end{cases}\]
不难发现以上等式左侧都是关于\(b1,b_2,\dots,b_t\)的轮换对称式，那么可以类比求解\(B_2\)的方法，利用\(\displaystyle (\sum_{i=1}^{100}i)^3 = 5050^3\)，得到\(\displaystyle \sum_{1\leq i < j <k \leq t} b_i b_j b_k = B_3\)，最终可以得到\(B_1,B_2,\dots,B_t\)共\(t\)个常数。上述推理的简单证明如下：
- 归纳奠基：显然通过\(\displaystyle(\sum_{i=1}^{100}i)^1=5050\)已经求得\(B_1\)；
- 归纳推理：设\(k\geq2\)，已知\(\displaystyle (\sum_{i=1}^ti)^k=5050^k\)以及\(B_1,B_2,\dots,B_{k-1}\)，而\(\displaystyle ((\sum_{i=1}^tb_i)+(5050-\sum_{i=1}^tb_i))^k\)的的展开式可由二项式定理求得为\(\displaystyle \sum_{j=0}^k C_k^j(\sum_{i=1}^tb_i)^{j}(5050-\sum_{i=1}^tb_i)^{k-j}\)，进一步展开后\((k+1)\)项中除了\(B_k\)未知之外，其余各项均已求得，因此可以求得\(B_k\)。
利用构造出的\(t\)个关于\(b_1,b_2,\dots,b_t\)即可根据系数构造一元\(t\)次方程：
\[\displaystyle \prod_{i=1}^t(x-b_i)=x^t-B_1x^{t-1}+\cdots+(-1)^tB_t=0\]
求解这个方程就可以得到被删除的\(t\)个数。
卡特兰数
卡特兰数的其中一个应用为：数\(1 \sim n\)按序入栈，求课内的出栈序列的个数。
卡特兰数的通项公式为\(C_n = \frac{C_{2n}^n}{n+1},n\in \text{N}^+\)。
求\(I=\lim\limits_{x \to 1^-} (1-x)^3 \displaystyle \sum_{n=1}^{\infty} n^2x^n\)
首先需要知道以下公式。 \[\displaystyle\sum_{n=0}^{\infty}x^n = \frac{1}{1-x}, x\in(-1,1)\]
对上式两端求导得到如下公式。 \[\displaystyle\sum_{n=0}^{\infty}(n+1)x^{n} = \frac{1}{(1-x)^2}, x\in(-1,1)\] \[\displaystyle\sum_{n=0}^{\infty}(n+1)(n+2)x^{n} = \frac{2}{(1-x)^3}, x\in(-1,1)\]
由\(n^2=(n+1)(n+2)-3(n+1)+1\)可以得到如下的结果。 \[\displaystyle \sum_{n=1}^{\infty} n^2x^n = \frac{2}{(1-x)^3} - \frac{3}{(1-x)^2} + \frac{1}{1-x} , x \in(-1,1)\]
最终可以得到\(I=2\)。
无穷级数中的下标变化问题
在前面求解过程中涉及到了两次求导，事实上隐含了两次下标变换，具体如下所示。
\[(\frac{1}{1-x})' = \displaystyle\sum_{n=1}^{\infty}nx^{n-1} = \displaystyle\sum_{n-1=0}^{\infty}[(n-1)+1]x^{n-1} = \displaystyle\sum_{n=0}^{\infty}(n+1)x^{n}, x\in(-1,1)\] \[[\frac{1}{(1-x)^2}]'= \sum_{n=1}^{\infty}n(n+1)x^{n-1}= \sum_{n-1=0}^{\infty}[(n-1)+1][(n-1)+2]x^{n-1} = \displaystyle\sum_{n=0}^{\infty}(n+1)(n+2)x^{n}, x\in(-1,1)\]
实际上，无穷级数的第一项需要分类讨论，因为对于\(f(x)=Cx^0\)，\(f'(x) \neq Cx^{-1}\)，而是\(f'(x)=0\)，因此需要分类讨论。
无穷集合势相关的证明
证明：\([0,1]\sim (0,1)\)
可以构造如下的\([0,1] \to (0,1)\)的双射，证毕。
\[f(x) = \begin{cases} \displaystyle \frac{1}{2}, x = 1\\ \displaystyle \frac{1}{4}, x = 0\\ \displaystyle \frac{1}{4}x, x = \frac{1}{2^n}, n \in \{1,2,3,\dots\}\\ \displaystyle x, \text{else}\\ \end{cases}\]
证明：\(|\text{N}^+| < |(0,1)|\)
参考康托对角线证明。
求 \(I=\displaystyle \lim\limits_{n \to \infty} \sum_{i=1}^{n} \frac{1}{n+i}\)
解法一
可以使用定积分定义求解。
\[ I = \displaystyle \frac{1}{n}\sum_{i=1}^{n} \frac{1}{1+ \displaystyle\frac{i}{n}} = \int_{0}^{1}\frac{1}{1+x}dx=\ln 2\]
解法二
由不等式\(\displaystyle \frac{x}{1+x} < \ln(1+x) < x\)，可以使用夹逼定理求解。
\[\displaystyle \frac{1}{n + 1} = \frac{\displaystyle \frac{1}{n}}{1 + \displaystyle \frac{1}{n}} < \ln(1 + \frac{1}{n}) =\ln(n+1) - \ln n < \frac{1}{n} \]
类推可以得到下列不等式。
\[\begin{cases} \displaystyle \frac{1}{n + 1} < \ln(n+1) - \ln n < \frac{1}{n}\\ \displaystyle \frac{1}{n + 2} < \ln(n+2) - \ln (n+1) < \frac{1}{n + 1}\\ \cdots\\ \displaystyle \frac{1}{2n} < \ln(2n) - \ln (2n-1) < \frac{1}{2n-1} \end{cases}\]
将以上\(n\)个不等式求和可得到如下不等式。
\[\displaystyle \sum_{i=1}^{n} \frac{1}{n+i} < \ln2 < \sum_{i=1}^{n} \frac{1}{n+i} + \frac{1}{n} - \frac{1}{2n} = \sum_{i=1}^{n} \frac{1}{n+i} + \frac{1}{2n}\]
进一步可知\(\displaystyle \ln2 - \frac{1}{2n} < \sum_{i=1}^{n} \frac{1}{n+i} < \ln2\)，故\(I=\ln2\)。
已知\(S=\{1,2,\dots,2000\}\)，求满足条件\(S_i \subseteq S\)且\(\displaystyle\sum_{e \in S_i}e \equiv 0 \pmod{5}\)的集合\(S_i\)的个数
题目来源于3Blue1Brown。
不妨首先考虑\(S'= \{1,2,3,4,5\}\)以及生成函数\(g(x) = (1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)\)，考虑\(g(x)\)展开式中\(x\)各个幂次前对应的系数：注意展开等号右侧的过程，\(x\)的幂次实际上说明了在展开过程中在\(5\)个括号中选择的\(x\)的幂次之和，这就表明\(x^i\)的系数\(c_i\)可以代表\(S'\)和为\(i\)的集合的个数，其中\(i \in \{0,1,\dots,15\}\)；同理，可以考虑生成函数 \(f(x) = \displaystyle \prod_{i=1}^{2000}(1+x^i) = \sum_{i=0}^{2000}c_ix^i\)。
基于上述分析，原问题可转化为求解和式\(\displaystyle \sum_{i \equiv 0 \pmod{5}}c_i\)的值。记\(T_j = \displaystyle \sum_{i \equiv j \pmod{5}}c_i, j \in \{ 0,1,2,3,4\}\)，那么下面需要求解\(T_0\)。
注意到\(f(1)=2^{2000}\)，\(f(-1)=0\)，根据这两个式子可以得到\(f(x)\)展开式中\(x\)的奇数次项和偶数次项前的系数和都是\(2^{1999}\)。受此启发，引入\(\zeta = e^{\displaystyle\frac{2\pi}{5}i}\)，计算\(f(\zeta^0)\)，\(f(\zeta^1)\)，\(f(\zeta^2)\)，\(f(\zeta^3)\)和\(f(\zeta^4)\)，由复数性质可得如下结果。
\[\begin{cases} f(\zeta^0)=T_0+T_1+T_2+T_3+T_4=2^{2000}\\ f(\zeta^1)=T_0+\zeta^1 T_1+\zeta^2T_2+\zeta^3T_3+\zeta^4T_4=2^{400}\\ f(\zeta^2)=T_0+\zeta^2 T_1+\zeta^4T_2+\zeta^1T_3+\zeta^3T_4=2^{400}\\ f(\zeta^3)=T_0+\zeta^3 T_1+\zeta^1T_2+\zeta^4T_3+\zeta^2T_4=2^{400}\\ f(\zeta^4)=T_0+\zeta^4 T_1+\zeta^3T_2+\zeta^2T_3+\zeta^1T_4=2^{400} \end{cases}\]
\(f(1)\)显然可得。下面将主要求解\(f(\zeta)\)，其余\(3\)个函数值同理可得，注意到\(\zeta\)是\(z^5-1=0\)的根，因此有\(z^5-1=\displaystyle\prod_{i=0}^{4}(z-\zeta^i)\)，令\(z=-1\)，则\(\displaystyle\prod_{i=0}^{4}(1+\zeta^i)=2\)，那么可以求解\(f(\zeta)\)如下所示。
\[f(\zeta)=[(1+\zeta^0)(1+\zeta^1)(1+\zeta^2)(1+\zeta^3)(1+\zeta^4)]^{400}=2^{400}\]
由\(\displaystyle\sum_{i=0}^4\zeta^i=0\)，对以上五个式子求和最终可得\(T_0=\displaystyle \frac{1}{5}(2^{2000} + 2^{400})\)。
已知方阵\(A\)和\(B\)满足关系\(AB=A+B\)，求证：\(AB=BA\)
\[AB=A+B \Rightarrow (A-E)(B-E)=E \Rightarrow (A-E)^{-1} = (B-E) \Rightarrow (A-E)(B-E) = (B-E)(A-E) \Rightarrow AB = BA\]
群论相关的一些证明
我比较喜欢这个课程。
已知\(<V,\cdot>\)为半群，且\(\forall a,b \in V, a \neq b \Rightarrow ab \neq ba\)，求证以下命题
- （1）\(V\)中幂等律成立
- （2）\(\forall a,b \in V, aba = a\)
- （3）\(\forall a,b,c \in V, abc = ac\)
（1）\(\forall a \in V\)，假定\(a \cdot a \neq a\)，那么\(a \cdot (a \cdot a) \neq (a \cdot a) \cdot a\)，对于满足结合律的半群而言产生矛盾，因此\(V\)中幂等律成立。
（2）\(\forall a,b \in V\)，假定\(aba \neq a\)，那么\(aba \cdot a \neq a \cdot aba\)，根据结合律和幂等律可知\(aba \neq aba\)，产生矛盾，因此命题成立。
（3）\(\forall a,b,c \in V\)，假定\(abc \neq ac\)，那么\(abc \cdot ac \neq ac \cdot abc\)，由结合律和（2）可知\(abc \neq abc\)，产生矛盾，因此命题成立。
抽象函数相关的题目
已知函数\(f(x)\)在\(\text{R}\)可导，且\(f(x+y)=e^yf(x)+e^xf(y)\)以及\(f'(0)=2\)，求\(f(x)\)的表达式
首先令\(x=y=0\)，得到\(f(0)=0\)。
再令\(y=\Delta x\)，那么\(f(x+\Delta x) - f(x) = (e^{\Delta x} - 1)f(x)+e^xf(\Delta x)\)。
由题目的\(f(x)\)处处可导及导数定义有： \[f'(x)=\lim_\limits{\Delta \to 0} \displaystyle \frac{f(x + \Delta x) - f(x)}{\Delta x}=f(x)\lim_\limits{\Delta \to 0}\frac { e^{\Delta x} - 1}{\Delta x} + e^x \lim_\limits{\Delta x \to 0} \frac{f(\Delta x) - f(0)}{\Delta x - 0}=f(x)+2e^x\]
求解微分方程得到\(f(x)=e^x(C+2x),C\in \text{R}\)。
对于微分方程\(\displaystyle \frac{dy}{dx} + P(x)y=Q(x)\)，其通解为\(y=e^{-\displaystyle \int P(x) dx}(C + \displaystyle \int e^{P(x)}Q(x)dx)\)。
已知\(A\)是实反对称矩阵，求证：\(B=(E-A)(E+A)^{-1}\)为正交矩阵
\[B^TB=[(E-A)(E+A)^{-1}]^T(E-A)(E+A)^{-1} = (E-A)^{-1}(E+A)(E-A)(E+A)^{-1}\]
注意到\((E-A)(E+A)=E-A^2=(E+A)(E-A)\)，因此\(B^TB=E\)，证毕。
事实上，只要\(B=\displaystyle\prod_{i} f_i(A)\)，其中\(A\)为方阵，那么\(f_{i_1}(A)\)与\(f_{i_2}(A)\)就可以交换乘积顺序。
求曲线\(x+y+e^y=0\)的渐近线
显然曲线\(x=-(e^y+y)\)只有斜渐近线，设之方程为\(x = ay+b\)。
\[a = \lim_\limits{y \to \infty} \displaystyle \frac{x}{y} = -1 - \lim_\limits{y \to \infty}\frac{e^y}{y}\]
以上极限仅在\(y\to -\infty\)时存在，并且\(a = -1\)。
\[b = \lim_\limits{y \to -\infty} \frac{x - ay}{y} = 0\]
因此所求渐近线方程为\(x+y=0\)。通过本题可知，不要局限地将任何惯用的因（自）变量符号默认当作因（自）变量。