高中奥数 2022-01-10

作者: 天目春辉 | 来源:发表于2022-01-10 07:38 被阅读0次

2022-01-10-01

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚等差数列与等比数列 P034 例4）

多项式 $f\left(x\right)=x^{n}+a_{1}x^{x-1}+\cdots+a_{n}$ ,其中 $a_{1},\cdots ,a_{n}\in \mathbb{R}$ .证明:在数 $\left|f\left(1\right)\right|,\left|f\left(2\right)\right|,\cdots ,\left|f\left(n+1\right)\right|$ .中必有一个数不小于 $-\dfrac{n}{2^{n}}$ .

证明

由定理1的结论,可知

$\Delta^{n}f\left(x\right)=\sum\limits_{i=0}^{n}\left(-1\right)^{i}\mathrm{C}_{n}^{i}f\left(x+n-i\right).\qquad(1)$

又由 $f\left(x\right)=x^{n}+a_{1}x^{x-1}+\cdots+a_{n}$ 可知 $\Delta^{n}f\left(x\right)=n!$ ,在(1)式中令 $x=1$ ,得

$n!=\sum\limits_{i=0}^{n}\left(-1\right)^{i}\mathrm{C}_{n}^{i}f\left(n+1-i\right).\qquad②$

如果命题不成立,那么对 $0\leqslant i\leqslant n$ ,都有 $\left|f\left(n+1-i\right)\right|<\dfrac{n!}{2^{n}}$ ,结合(2)将有

$n!\leqslant \sum\limits_{i=0}^{n}\left|\left(-1\right)^{i}\mathrm{C}_{n}^{i} f\left(n+1-i\right)\right|<\sum\limits_{i=0}^{n}\mathrm{C}_{n}^{i}\cdot\dfrac{n!}{2^{n}}=n!,$

矛盾.

所以,命题成立.

说明此题亦可利用Lagrange插值公式去处理.

2022-01-10-01

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚等差数列与等比数列 P035 例5）

对非负整数 $N$ ,用 $u\left(N\right)$ 表示 $N$ 在二进制表示下数码1出现的次数(例如 $u\left(10\right)=2$ ,因为在二进制表示下 $10=\left(1010\right)_{2}$ ).用 $\deg p\left(x\right)$ 表示多项式 $p\left(x\right)$ 的次数.证明:对任意 $k\in \mathbb{N}^{*}$ ,都有

$\sum\limits_{i=0}^{2^{k}-1}\left(-1\right)^{u\left(i\right)}p\left(i\right)=\begin{cases} 0,&\text{若}\deg p\left(x\right)<k;\\ \left(-1\right)^{k}\alpha\cdot k!\cdot 2^{\frac{k\left(k-1\right)}{2}},&\text{若}\deg p\left(x\right)=k. \end{cases}$

这里 $\alpha$ 为 $p\left(x\right)$ 的首项系数.

证明

利用差分方法处理.

对 $t\in \mathbb{N}^{*}$ ,记 $\Delta_{t}\left(p\left(x\right)\right)=p\left(x\right)-p\left(x+t\right)$ ,则

$q_{k}\left(x\right)=\Delta _{1}\left(\Delta _{2}\left(\delta_{4}\cdots\left(\Delta _{2^{k-1}}\left(p\left(x\right)\right)\right)\cdots\right)\right),$

也是关于 $x$ 的多项式.

我们对 $k$ 归纳来证明:

$\sum\limits_{i=0}^{2^{k}-1}\left(-1\right)^{u\left(i\right)}p\left(i\right)=q_{k}\left(0\right).\qquad(2)$

当 $k=1$ 时,(1)式左边 $=p\left(0\right)-p\left(1\right)$ ,右边为 $q_{1}\left(0\right)=p\left(0\right)-p\left(1\right)$ .所以,(1)对 $k=1$ 成立.

现设(1)对 $k$ 成立,考虑 $k+1$ 的情形,此时

$\begin{aligned} \sum_{i=0}^{2^{k+1}-1}(-1)^{u(i)} p(i) &=\sum_{i=0}^{2^{k}-1}(-1)^{u(i)} p(i)+\sum_{i=2^{k}}^{2^{k+1}-1}(-1)^{u(i)} p(i) \\ &=\sum_{i=0}^{2^{k}-1}(-1)^{u(i)} p(i)-\sum_{i=0}^{2^{k}-1}(-1)^{u(i)} p\left(2^{k}+i\right) \\ &=\sum_{i=0}^{2^{k}-1}(-1)^{u(i)}\left(p(i)-p\left(2^{k}+i\right)\right) \\ &=\sum_{i=0}^{2^{k}-1}(-1)^{u(i)} \Delta_{2^{k}}(p(i)) . \end{aligned}$

现在用 $\Delta _2^{k}\left(p\left(x\right)\right)$ 代替 $p\left(x\right)$ ,对它用归纳假设,可知

$\sum_{i=0}^{2^{k+1}-1}(-1)^{u(i)} p(i)=q_{k}\left(\Delta_{2^{k}}(p(0))\right)=q_{k+1}(0).$

所以,对 $k\in \mathbb{N}^{*}$ ,(1)都成立.

注意到,当 $\deg\left(p\left(x\right)\right)\leqslant k$ 时,对 $p\left(x\right)$ 每作一次差分,其次数就减少1,故当 $\deg p\left(x\right)<k$ 时,有 $q_{k}\left(x\right)=0$ .而当 $\deg p\left(x\right)=k$ 时,由于对 $t\in \mathbb{N}^{*}$ ,有

$\begin{aligned} \Delta_{t}(p(x)) &=p(x)-p(x+t) \\ &=\alpha\left(x^{k}-(x+t)^{k}\right)+\beta\left(x^{k-1}-(x+t)^{k-1}\right)+\cdots, \end{aligned}$

利用二项式定理,知 $\Delta _{t}\left(p\left(x\right)\right)$ 是一个首项系数为 $atk$ 的 $k-1$ 次多项式.从而, $q_{k}\left(x\right)$ 是常数多项式,且

$\begin{aligned} q_{k}(x) &=\left(\prod_{j=0}^{k-1}\left(-(j+1) \cdot 2^{j}\right)\right) \cdot \alpha \\ &=(-1)^{k} \cdot 2^{\frac{k(k-1)}{2}} \cdot k ! \cdot \alpha \end{aligned}$

从而,命题成立.

说明这里取 $p\left(x\right)$ 为不同的 $k$ 次多项式,可得到不同的恒等式.

2022-01-10-03

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚等差数列与等比数列 P036 例6）

设 $\left\{a_{n}\right\}$ 、 $\left\{b_{n}\right\}$ 是两个数列,证明下面的二项式反演公式:对任意 $n\in \mathbb{N}^{*}$ ,都有 $a_{n}=\sum\limits_{k=0}^{n}\mathrm{C}_{n}^{k}b_{k}$ 的充要条件是对任意 $n\in \mathbb{N}^{*}$ ,都有 $b_{n}=\sum\limits_{k=0}^{n}\left(-1\right)^{n-k}\mathrm{C}_n^{k}a_{k}$ .

正明

对 $m\in \mathbb{N}^{*}$ ,设 $f\left(x\right)$ 是一个 $m$ 次多项式,且对 $0\leqslant k\leqslant m$ ,都有 $f\left(k\right)=a_{k}$ .

利用例2中的差分多项式,可知

$f\left(x\right)=\sum\limits_{k=0}^{m}\Delta^{k}f\left(0\right)\left(\begin{array}{c} x\\ k \end{array}\right).$

令 $g\left(x\right)=\sum\limits_{k=0}^{m}b_{k}\left(\begin{array}{c} x\\ k \end{array}\right)$ ,则 $g\left(x\right)$ 也是一个 $m$ 次多项式.

如果对任意 $n\in \mathbb{N}^{*}$ ,都有 $a_{n}=\sum\limits_{k=0}^{n}\mathrm{C}_{n}^{k}b_{k}$ ,那么对任意 $0\leqslant n\leqslant m$ ,都有 $g\left(n\right)=\sum\limits_{k=0}^{n}\mathrm{C}_{n}^{k}b_{k}=a_{n}=f\left(n\right)$ ,这表明 $f\left(x\right)-g\left(x\right)$ 有 $m+1$ 个不同的根 $\left(x=0,1,2,\cdots,m\right)$ ,从而它是一个零多项式,所以 $b_{n}=\Delta^{n}f\left(0\right)$ .结合定理1的结论,就有

$\begin{aligned} b_{n} &=\Delta^{n} f(0)=\sum_{k=0}^{n}(-1)^{n-k} \mathrm{C}_{n}^{k} f(k) \\ &=\sum_{k=0}^{n}(-1)^{n-k} \mathrm{C}_{n}^{k} a_{k} \end{aligned}$

反过来,如果对任意 $n\in \mathbb{N}^{*}$ ,都有 $b_{n}==\sum_{k=0}^{n}(-1)^{n-k} \mathrm{C}_{n}^{k} a_{k}$ ,因而有 $g\left(x\right)=f\left(x\right)$ ,所以 $a_{n}=f\left(n\right)=g\left(n\right)=\sum\limits_{k=0}^{m}\mathrm{C}_{n}^{k}b_{k}=\sum\limits_{k=0}^{n}\mathrm{C}_{n}^{k}b_{k}$ (注意,这时要取 $m\geqslant n$ ).