高中数学 2022-01-24

2022-01-24 本文已影响0人天目春辉

2022-01-24-01

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚习题一 P055 习题37）

数列 $\left\{p_{n}\right\}$ 满足 $p_{1}=2$ , $p_{2}=5$ , $p_{n+2}=2p_{n+1}+p_{n}$ , $n=1,2,\cdots$ .

证明:对任意正整数 $n$ ,都有

$p_{n}=\sum \dfrac{\left(i+j+k\right)!}{i!j!k!}.$

这里求和对满足 $i+j+2k=n$ 的所有非负整数组 $\left(i,j,k\right)$ 进行.

证明

构造一个组合模型:用 $f\left(n\right)$ 表示由 $1\times 1$ 的红色方块, $1\times 1$ 的蓝色方块和 $1\times 2$ 的白色方块拼成的 $1\times n$ 的长条的数目.

直接计算可知

$f\left(n\right)=\sum\dfrac{\left(i+j+k\right)!}{i!j!k!}.$

这里的求和对 $i+j+2k=n$ 的所有非负整数组 $(i,j,k)$ 进行.

另一方面,采用递推方法来计算 $f\left(n\right)$ ,可知 $f\left(1\right)=2$ , $f\left(2\right)=5$ ,而对长为 $n+2$ 的 $1\times \left(n+2\right)$ 的长条,如果第一个小方块为红色或蓝色,去掉后共有 $f\left(n+1\right)$ 个符合条件的长条;如果第一个小方块为白色(其长度为2),去掉后共有 $f\left(n\right)$ 个符合条件的长条,故 $f\left(n+2\right)=2f\left(n+1\right)+f\left(n\right)$ .

对比数列 $\left\{f\left(n\right)\right\}$ 与 $\left\{p_{n}\right\}$ 的初始值和递推关系式可知对任意 $n\in \mathbb{N}*$ ,都有 $f\left(n\right)=p_{n}$ .

所以,命题成立.

2022-01-24-02

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚习题一 P055 习题38）

记 $A_{n}=\left\{1+\dfrac{\alpha_{1}}{\sqrt{2}}+\cdots\dfrac{a_{n}}{\left(\sqrt{2}\right)^{n}}\bigg| \alpha_{i}=1\text{或}-1,\text{这里}i=1,2,\cdots,n\right\}$ .

(i)对每个正整数 $n$ ,求集合 $A_{n}$ 中不同元素的个数;

(ii)对每个正整数 $n$ ,求集合 $A_{n}$ 中任意两个不同元素之积的和.

解

引理对任意 $n\in \mathbb{N}^{*}$ ,都有

$\begin{aligned} &\left\{\dfrac{\beta_{1}}{2}+\dfrac{\beta_{2}}{2^{2}}+\cdots+\dfrac{\beta_{n}}{2^{n}} \bigg| \beta_{i} \in\{-1,1\}, i=1,2, \cdots, n\right\} \\ =&\left\{\dfrac{j}{2^{n}} \bigg| j \text { 为奇数,且 }\left|j\right|<2^{n}\right\} . \end{aligned}$

引理的证明可通过对 $n$ 归纳来处理.

当 $n=1$ 时,引理显然成立.现设引理对所有小于 $n$ 的正整数成立,考虑 $n$ 的情形.

对 $\beta_{i}\in \left\{-1,1\right\}$ ,记 $j=2^{n-1}\beta_{1}+2^{n-2}\beta_{2}+\cdots+2^{0}\beta_{n}$ ,则 $\sum\limits_{i=1}^{n}\dfrac{\beta_{i}}{2^{i}}=\dfrac{j}{2^{n}}$ ,并且,并且 $j$ 为奇数.进一步,还有

$\left|\dfrac{j}{2^{n}}\right|= \left|\sum\limits_{i=1}^{n} \dfrac{\beta_{i}}{2^{i}}\right| \leqslant \sum\limits_{i=1}^{n} \dfrac{\left|\beta_{i}\right|}{2^{i}} =\sum\limits_{i=1}^{n} \dfrac{1}{2^{i}}=1-\dfrac{1}{2^{n}}<1,$

故 $\left|j\right|<2^{n}$ .

反过来,对 $j$ 为奇数,且 $\left|j\right|<2^{n}$ .注意到 $\dfrac{j-1}{2}$ 与 $\dfrac{j+1}{2}$ 具有不同的奇偶性,我们设 $j_{0}$ 是 $\dfrac{i-1}{2}$ 和 $\dfrac{i+1}{2}$ 中的那个奇数.

则 $\left|j_{0}\right|\leqslant \dfrac{1}{2}\left(1+\left|j\right|\right)\leqslant 2^{n-1}+\dfrac{1}{2}$ ,结合 $j_{0}$ 为奇数,知 $\left|j_{0}\right|<2^{n-1}$ .

从而由归纳假设知,存在 $\beta_{1},\beta_{2},\cdots ,\beta_{n-1}\in \left\{-1,1\right\}$ ,使得

$\dfrac{\beta_{1}}{2}+\dfrac{\beta_{2}}{2^{2}}+\cdots+\dfrac{\beta_{n-1}}{2^{n-1}}=\dfrac{j_{0}}{2^{n-1}},$

令 $\beta_{n}=j-2j_{0}$ ,则 $\beta_{n}\in \left\{-1,1\right\}$ ,并且

$\sum\limits_{i=1}^{n}\dfrac{\beta_{i}}{2_{i}}=\dfrac{j_{0}}{2^{n-1}}+\dfrac{j-2j_{0}}{2^{n}}=\dfrac{j}{2^{n}}.$

所以,引理获证

(i)由引理的结论及 $A_{n}$ 中元素的结构,可知 $A_{n}=\left\{1+\dfrac{j}{2^{\lfloor\frac{n}{2}\rfloor}}+\dfrac{k}{2^{\lceil\frac{n}{2}\rceil}}\sqrt{2}\bigg| j,k\text{为奇数},\text{且}\left|j\right|<2^{\lfloor\frac{n}{2}\rfloor},k<2^{\lceil\frac{n}{2}\rceil}\right\}$ ,所以,由 $\sqrt{2}$ 为无理数,可知 $\left|A\right|=2^{\lfloor\frac{n}{2}\rfloor}\cdot 2^{\lceil\frac{n}{2}\rceil}=2^{n}$ .

(ii)记 $S=\sum_{a, b \in A_{n} \atop a<b} a b$ ,那么 $S=\frac{1}{2}\left(\left(\sum_{a \in A_{n}} a\right)^{2}-\sum_{a \in A_{n}} a^{2}\right)$ .

将 $A_{n}$ 中的元素 $1+\dfrac{j}{2^{\lfloor\frac{n}{2}\rfloor}}+\dfrac{k}{2^{\lceil\frac{n}{2}\rceil}}\sqrt{2}$ 与 $1-\dfrac{j}{2^{\lfloor\frac{n}{2}\rfloor}}-\dfrac{k}{2^{\lceil\frac{n}{2}\rceil}}\sqrt{2}$ 配对求和,用(i)的结论,可知 $\sum\limits_{a \in A_{n}} a=2^{n}$ .

进一步,利用结论:若 $X$ 、 $Y$ 都是有限集,且 $\sum\limits_{x\in X}x=\sum\limits_{y\in Y}y=0$ ,则 $\sum\limits_{x \in X} \sum\limits_{y \in Y}(1+x+y)^{2}=|X| \cdot|Y|+|Y| \cdot \sum\limits_{x \in X} x^{2}+|X| \cdot \sum\limits_{y \in Y} y^{2}$ .结合 $A_{n}$ 的结构,可得

$\begin{aligned} &\sum\limits_{a \in A_{n}} a^{2}=\sum\limits_{j \text { 为奇数 }\atop \left|j\right|<2^{\lfloor \frac{n}{2}\rfloor}}\sum\limits_{k \text { 为奇数 }\atop\left|k\right|<2^{\lceil\frac{n}{2}\rceil}}\left(1+\frac{j}{2^{\lfloor\frac{n}{2}\rfloor}}+\frac{k}{2^{\lceil\frac{n}{2}\rceil}} \sqrt{2}\right)^{2}\\ &=2^{\lceil\frac{n}{2}\rceil} \cdot 2^{\lfloor\frac{n}{2}\rfloor}+\sum\limits_{j \text { 为奇数 } \atop \left|j\right|<2^{\lfloor\frac{n}{2}\rfloor}} \dfrac{j^{2} \cdot 2^{\lceil\frac{n}{2}\rceil}}{2^{\lfloor \frac{n}{2}\rfloor}}+\sum\limits_{k \text { 为奇数 } \atop \left|k\right|<2^{\lceil\frac{n}{2}\rceil}} \dfrac{2 k^{2} \cdot 2^{\lfloor\frac{n}{2}\rfloor}}{2^{2\lceil\frac{n}{2}\rceil}}\\ &=2^{n}+\dfrac{1}{3}\left(\frac{2^{\lceil\frac{n}{2}\rceil} \cdot 2^{\lfloor\frac{n}{2}\rfloor}\left(2^{2\lfloor\frac{n}{2}\rfloor}-1\right)}{2^{2\lfloor\frac{n}{2}\rfloor}}+\frac{2^{\lfloor\frac{n}{2}\rfloor} \cdot 2^{\lceil\frac{n}{2}\rceil}\left(2^{2\lceil\frac{n}{2}\rceil}-1\right)}{2^{2\lceil\frac{n}{2}\rceil -1}}\right)\\ &=2^{n}+\dfrac{2^{n}}{3}\left(3-\dfrac{1}{2^{2\lfloor\frac{n}{2}\rfloor}}-\dfrac{1}{2^{2\lceil\frac{n}{2}\rceil-1}}\right)\\ &=2^{n+1}-1 . \end{aligned}$

综上,(i)的答案是 $2^{n}$ ,而(ii)的答案为 $\dfrac{1}{2}\left(2^{2n}-2^{n+1}+1\right)$ .

2022-01-24-03

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚习题一 P055 习题39）

数列 $\left\{x_{n}\right\}$ 定义如下

$x_{0}=4,x_{1}=x_{2}=0,x_{3}=3,x_{n+4}=x_{n}+x_{n+1},n=0,1,2,\cdots.$

证明:对任意素数 $p$ ,都有 $p\mid x_{p}$ .

证明

引理设 $n\in \mathbb{N}^{*}$ ,将 $n$ 表示为若干个3或4之和的有序分拆排成一个矩阵,则 $x_{n}$ 为该矩阵中第一列上各数之和.

例如:当 $n=15$ 时,所得的矩阵为

$\begin{array}{lllll} 4, & 4, & 4, & 3 & \\ 4, & 4, & 3, & 4 & \\ 4, & 3, & 4, & 4 & \\ 3, & 4, & 4, & 4 & \\ 3, & 3, & 3, & 3,& 3 \end{array}$

而直接由递推式可算得 $x_{15}=18$ 等于上述矩阵中第一列各数之和.

引理的证明:对 $n$ 归纳来证,当 $n=1,2,3,4$ 时直接验证可知命题成立.

现设引理对所有小于 $n\left(\geqslant 5\right)$ 的下标都成立,考虑 $n$ 的情形.

依 $n$ 表为3或4的有序分拆的最后一项为3、4分为两类:末项为3的有序分拆全部去掉末项3后得到 $n-3$ 的所有有序分拆;末项为4的全部去掉末项4后得到 $n-4$ 的所有有序分拆.

结合 $n\geqslant 5$ ,其分拆若存在,则至少有两项,可知 $n$ 的有序分拆构成的矩阵的第一列上各数之和为 $x_{n-3}+x_{n-4}$ (这里用到归纳假设),故引理对 $n$ 成立,命题获证.

回到原题,当 $p=2,3$ 时 $x_{p}=0$ ,命题成立,对素数 $p\left(\geqslant 5\right)$ ,设将 $p$ 表为3或4的有序分拆作出的矩阵为 $M$ ,则 $M$ 的每一行的长度l满足 $\dfrac{p}{4} \leqslant l\leqslant \dfrac{p}{3}$ .

对 $M$ 中长度相同的行合成的子矩阵 $\mathbf{T}$ 作下面的分析:设 $\mathbf{T}$ 中第一列的元素和为 $S$ ,由于 $\mathbf{T}$ 的每一行中必同时出现3和4(仅出现3或4时, $p$ 是3或4的倍数,不为素数),从而将该行中的这对3和4对换位置所得的 $p$ 的分拆是 $\mathbf{T}$ 的另一行.

这表明: $\mathbf{T}$ 中任意两列上的元素和相同(因为这两列上对应位置上的数,如果不同,那么必有另一行与此两列交出的数正好是它们的对换),记 $\mathbf{T}$ 中每一列的和为 $S$ .设 $\mathbf{T}$ 的列数为l,则 $\mathbf{T}$ 中所有数之和为 $sl$ ,而 $\mathbf{T}$ 中每一行中所有数之和都为 $p$ ,故 $sl$ 是 $p$ 的倍数,结全 $\dfrac{p}{4} \leqslant l\leqslant \dfrac{p}{3}$ ,可知 $p\mid s$ .

依上述讨论可得,对M中第一列上各数之和而言,它也是 $p$ 的倍数,即有 $p\mid x_{p}$ .

命题成立.

2022-01-24-04

（来源: 数学奥林匹克小丛书第二版高中卷数列与数学归纳法冯志刚习题一 P055 习题40）

求所有的正整数数列 $a_{0},a_{1},\cdots ,a_{n}$ ,使得

(i) $\dfrac{a_{0}}{a_{1}}+\dfrac{a_{1}}{a_{2}}+\cdots+\dfrac{a_{n-1}}{a_{n}}=\dfrac{99}{100}$ ;

(ii) $a_{0}=1$ ,且 $\left(a_{k+1}-1\right)a_{k-1}\geqslant a_{k}^{2}\left(a_{k}-1\right),k=1,2,\cdots ,n-1$ .

解

设 $a_{1},\cdots ,a_{n}$ 是符合条件的正整数,则由(i)可知对 $1\leqslant k\leqslant n$ ,都有 $a_{k}>a_{k-1}$ (否则左边 $\geqslant 1$ ,而右边 $<1$ ),从而,有 $a_{k}>1$ ,于是,由(ii)知

$\dfrac{a_{k}-1}{a_{k}\left(a_{k}-1\right)}\geqslant \dfrac{a_{k}}{a_{k+1}-1},$

即 $\dfrac{a_{k-1}}{a_{k}-1}-\dfrac{a_{k-1}}{a_{k}}\geqslant \dfrac{a_{k}}{a_{k+1}-1}$ ,所以 $\dfrac{a_{k-1}}{a_{k}}\leqslant \dfrac{a_{k-1}}{a_{k}-1}-\dfrac{a_{k}}{a_{k+1}-1}$ ,对 $k=i+1,\cdots,n-1$ 求和,就有

$\dfrac{a_{i}}{a_{i+1}}+\cdots+\dfrac{a_{n-1}}{a_{n}}\leqslant \dfrac{a_{i}}{a_{i+1}-1}-\dfrac{a_{n-1}}{a_{n}-1}+\dfrac{a_{n-1}}{a_{n}}<\dfrac{a_{i}}{a_{i+1}-1}.\qquad(1)$