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 выпуск)

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *