高中奥数 2022-01-25

2022-01-25 本文已影响0人不为竞赛学奥数

2022-01-25-01

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

数列 $\left\{y_{n}\right\}$ 定义如 $y_{2}=y_{3}=1$ ,且

$\left(n+1\right)\left(n-2\right)y_{n+1}=n\left(n^{2}-n-1\right)y_{n}-\left(n-1\right)^{3}y_{n-1}.,n=3,4,\cdots$

证明: $y_{n}$ 为整数的充要条件是 $n$ 为素数.

证明

令 $x_{n}=ny_{n}$ , $n=2,3,\cdots$ ,则 $x_{2}=2$ , $x_{3}=3$ ,且当 $n\geqslant 3$ 时,有 $\left(n-2\right)x_{n+1}=\left(n^{2}-n-1\right)x_{n}-\left(n-1\right)^{2}x_{n-1}$ ,即

$\dfrac{x_{n-1}-x_{n}}{n-1}=\left(n-1\right)\cdot\dfrac{x_{n}-x_{n-1}}{n-2}.\qquad(1)$

利用(1)递推可得

$\begin{aligned} \dfrac{x_{n+1}-x_{n}}{n-1} &=(n-1) \cdot \dfrac{x_{n}-x_{n-1}}{n-2}\\ &=(n-1)(n-2) \cdot \dfrac{x_{n-1}-x_{n-2}}{n-3} \\ &=\cdots\\ &=(n-1) \cdots 2 \cdot \dfrac{x_{3}-x_{2}}{1}\\ &=(n-1) ! \end{aligned}$

得 $x_{n+1}-x_{n}=n!-\left(n-1\right)!$ ,裂项求和,知 $x_{n}=x_{2}+\sum\limits_{k=2}^{n-1}\left(x_{k+1}-x_{k}\right)=x_{2}+\sum\limits_{k=2}^{n-1}\left(k!-\left(k-1\right)!\right)=x_{2}+\left(n-1\right)!-1=\left(n-1\right)!+1$ .

结合Wilson定理:当且仅当 $n$ 为素数时, $n\mid \left(n-1\right)!+1$ ,可知 $y_{n}\in \mathbb{Z}$ 的充要条件是 $n$ 为素数.

2022-01-25-02

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

给定素数 $p>3$ ,令 $q=p^{3}$ .定义数列 $a_{n}$ 如下

$a_{n}=\begin{cases} n,&n=0,1,2,\cdots,p-1,\\ a_{n-1}+a_{n-p},&n>p-1. \end{cases}.$

求 $a_{q}$ 除以 $p$ 所得的余数.

解

引理设 $n$ 、 $k\in \mathbb{N}^{*}$ , $n\geqslant kp$ ,则

$a_{n}=\sum\limits_{i=0}^{k}\mathrm{C}_{k}^{i}a_{n-i\left(p-1\right)-k}.\qquad(1)$

对 $k$ 归纳予以证明.当 $k=1$ 时,(1)就是 $a_{n}=a_{n-1}+a_{n-p}$ ,故(1)对 $k=1$ 成立.

现设(1)对k成立,考虑 $k+1$ 的情形.此时 $n\geqslant \left(k+1\right)p$ ,下标 $n-i\left(p-1\right)-k\left(0\leqslant i\leqslant k\right)$ 的最小值在 $i=k$ 时取到,该最小值为 $n-kp\geqslant p$ ,所以,下面求和式中的每一项都可用条件中的递推式.

由归纳假设知,当 $n\geqslant \left(k+1\right)p$ 时,有

$\begin{aligned} a_{n} &=\sum\limits_{i=0}^{k} \mathrm{C}_{k}^{i} a_{n-i(p-1)-k} \\ &=\sum\limits_{i=0}^{k} \mathrm{C}_{k}^{i}\left(a_{n-i(p-1)-k-1}+a_{n-i(p-1)-k-p}\right) \\ &=\mathrm{C}_{k}^{0} a_{n-k-1}+\sum\limits_{i=1}^{k} \mathrm{C}_{k}^{i} a_{n-i(p-1)-k-1}+\sum\limits_{i=0}^{k-1} \mathrm{C}_{k}^{i} a_{n-i(p-1)-k-p}+\mathrm{C}_{k}^{k} a_{n-(k+1) p} \\ &=\mathrm{C}_{k+1}^{0} a_{n-(k+1)}+\sum\limits_{i=0}^{k-1} \mathrm{C}_{k}^{i+1} a_{n-(i+1)(p-1)-(k+1)}+\sum\limits_{i=0}^{k-1} \mathrm{C}_{k}^{i} a_{n-(i+1)(p-1)-(k+1)}+\mathrm{C}_{k+1}^{k+1} a_{n-(k+1) p} \\ &=\mathrm{C}_{k+1}^{0} a_{n-(k+1)}+\sum\limits_{i=0}^{k-1}\left(\mathrm{C}_{k}^{i+1}+\mathrm{C}_{k}^{i}\right) a_{n-(i+1)(p-1)-(k+1)}+\mathrm{C}_{k+1}^{k+1} a_{n-(k+1) p} \\ &=\sum\limits_{i=0}^{k+1} \mathrm{C}_{k+1}^{i} a_{n-(i+1)(p-1)-(k+1)} . \end{aligned}$

最后一步,用到 $\mathrm{C}_{k}^{i+1}+\mathrm{C}_{k}^{i}=\mathrm{C}_{k+1}^{i+1}$ .

所以,(1)对 $k+1$ 成立,引理获证.

下面利用引理来处理原题.

当 $n\geqslant p^{2}$ 时,在引理中令 $k=p$ ,就有

$a_{n}=\sum\limits_{i=0}^{p} \mathrm{C}_{p}^{i} a_{n-i(p-1)-p}$

熟知,当 $1\leqslant i\leqslant p-1$ 时,有 $\mathrm{C}_{p}^{i}\equiv 0\left(\bmod p\right)$ ,所以, $a_{n}\equiv a_{n-p}+a_{n-p^{2}}\left(\bmod p\right)$ ,这时结合 $a_{n}=a_{n-1}+a_{n-p}$ ,可得 $a_{n-1}\equiv a_{n-p^{2}}\left(\bmod p\right)$ ,这表明对任意 $t\geqslant p^{2}-1$ ,有 $a_{t}\equiv a_{t+p^{2}-1}\left(\bmod p\right)$ .

由于 $p^{3}=p\left(p^{2}-1\right)+p$ ,故 $a_{p^{3}}=a_{p+p\left(p^{2}-1\right)}\equiv a_{p}\left(\bmod p\right)$ ,而 $a_{p}=a_{0}+a_{p-1}=p-1$ ,所以 $a_{p^{3}}\equiv p-1\left(\bmod p\right)$ ,即 $a_{p^3}$ 除以 $p$ 所得的余数为 $p-1$ .

2022-01-25-03

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

设 $n$ 为不小于2的正整数, $2\leqslant b_{0}\leqslant 2n-1$ , $b_{0}$ 为整数,考虑由递推式

$\b_{i+1}=\begin{cases} 2b_{i}-1,&\text{若}b_{i}\leqslant n,\\ 2b_{i}-2n,&\text{若}b_{i}>n \end{cases}$

定义的数列 $\left\{b_{i}\right\}$ .用 $p\left(b_{0},n\right)$ 表示满足 $b_{p}=b_{0}$ 的最小下标 $p$ .

(i)设 $k$ 为给定的正整数,求 $p\left(2,2^{k}\right)$ 和 $p\left(2,2^{k}+1\right)$ 的值;

(ii)证明:对任意 $n$ 和 $b_{0}$ 都有 $p\left(b_{0},n\right)\mid p\left(2,n\right)$ .

解

为方便计,记 $m=n-1$ , $b_{i}=a_{i}+1$ ,则 $1\leqslant a_{0}\leqslant 2m$ ,且

$a_{i+1}=\begin{cases} 2a_{i},&\text{若}a_{i}\leqslant m,\\ 2a_{i}-\left(2m+1\right),&\text{若}a_{i}>m. \end{cases}$

这表明 $a_{i+1}\equiv 2a_{i}\left(\bmod 2m+1\right)$ ,且 $1\leqslant a_{i}\leqslant 2m,i=1,2,\cdots.$

(i)题中的 $p\left(2,2^{k}\right)$ 和 $p\left(2,2^{k}+1\right)$ 等价于针对 $\left\{a_{i}\right\}$ 求 $p\left(1,2^{k}-1\right)$ 和 $p\left(1,2^{k}\right)$ .

前者等价于求最小 $l\in \mathbb{N}^{*}$ ,使得 $2^{l}\equiv 1\left(\bmod 2\left(2^{k}-1\right)+1\right)$ ,后者等价于求最小的 $l\in \mathbb{N}^{*}$ ,使得 $2^{l}\equiv 1\left(\bmod 2^{k+1}+1\right)$ .

显然 $2^{k+1}\equiv 1\left(\bmod 2\left(2^{k}-1\right)+1\right)$ ,而对 $1\leqslant t\leqslant k$ ,都有 $1\leqslant 2^{t}-1<2^{k-1}-1=2\left(2^{k}-1\right)+1$ ,故 $p\left(1,2^{k}-1\right)=k+1$ .

又 $2^{2\left(k+1\right)}\equiv 1\left(\bmod2^{k+1}+1\right)$ ,从而 $p\left(1,2^{k}\right)\mid 2\left(k+1\right)$ ,又对 $1\leqslant t\leqslant k+1$ ,都有 $1\leqslant 2^{t}-1<2^{k+1}+1$ ,于是 $p\left(1,2^{k}\right)>k+1$ ,故 $p\left(1,2^{k}\right)=2\left(k+1\right)$ .

所以,针对 $\left\{b_{i}\right\}$ 有 $p\left(2,2^{k}\right)=k+1$ , $p\left(2,2^{k}+1\right)=2\left(k+1\right)$ .

(ii)还是转到 $\left\{a_{i}\right\}$ 上讨论,要求证明: $\left(a_{0},m\right)\mid p\left(1,m\right)$ .

现设 $p\left(1,m\right)=t$ ,则 $2^{t}\equiv 1\left(\bmod 2m+1\right)$ ,从而 $2^{t}a_{0}\equiv a_{0}\left(\bmod 2m+1\right)$ ,这表明 $p\left(a_{0},m\right)\mid t$ (这里用到类似于初等数论中阶的性质),即有 $p\left(a_{0},m\right)\mid p\left(1,m\right)$ ,命题成立.

高中奥数 2022-01-25

猜你喜欢

热点阅读