M1437 — ПриМат

Докажите, что если последовательность удовлетворяет следующим условиям:

$a_{1}, a_{2}, a_{3}$ — целые неотрицательные числа;

$a_{n+3}=a_{n+1}+a_{n}$ (при

$n = 1, 2, …$ ),

То при всех натуральных $n$ и простых $p$ число $a_{n+3p+1}-a_{n+p+1}-a_{n+1}$ делится на $p$ .

Решение

Как известно, числа $C_{n}^{k}=\frac{n(n-1)…(n-k+1)}{1\cdot 2\cdot …\cdot k}$ (биноминальные коэффициенты) целые, причем $C_{n-1}^{k}+C_{n-1}^{k+1}=C_{n}^{k+1}$ . Достаточно доказать, что при произвольном натуральном $p$

$a_{n+3p}=\sum_{j=0}^{p}C_{p}^{j}a_{n+j}$

При $p=1$ равенство очевидно. Пусть оно верно при $p-1$ . Имеем:

$a_{n+3p}=a_{n_3(p-1)}+a_{(n+1)+3(p-1)}=\sum_{j=0}^{p-1}C_{p-1}^{j}a_{n+j}+\sum_{j=0}^{p-1}C_{p-1}^{j}a_{n+1+j}$

Для завершения доказательства достаточно воспользоваться равенством $C_{p-1}^{j}+C_{p-1}^{j-1}=C_{p}^{j}$ и тем, что $C_{p}^{i}$ делится на $p$ при простом $p$ .

Другое решение можно получить, используя тот факт, что $a_{n}=\lambda_{1}x_{1}^{n}+\lambda_{2}x_{2}^{n}+\lambda_{3}x_{3}^{n}$ , где $x_{i}$ — корни уравнения $x^{3}-x-1=0$ .

$A=a_{n+3p+1}-a_{n+p+1}-a_{n+1}=\sum_{i=1}^{3}\lambda_{i}x_{i}^{n+1}(x_{i}^{3})^{p}-\sum_{i=1}^{3}\lambda_{i}x_{i}^{n+1}x_{i}^{p}-\sum_{i=1}^{3}\lambda_{i}x_{i}^{n+1}$ .

Поэтому

$A=\sum_{i=1}^{3}\lambda_{i}x_{i}^{n+1}(x_{i}+1)^{p}-…=\sum_{j=1}^{p-1}C_{p}^{j}(\sum_{i=1}^{3}\lambda_{i}x_{i}^{n+1+j})$ .

Но, поскольку $p$ — простое число. $C_{p}^{j}$ делится на $p$ ; число в скобках равно $a_{n+1+j}$ , следовательно, оно целое.

Замечание. Из решения следует, что в условиях задачи число 3 можно заменить любым натуральным числом, большим 1.

Д.Андриенко, В.Сендеров

Журнал Квант (1994г, 6 выпуск)

Добавить комментарий

Решение

Добавить комментарий Отменить ответ