M1437

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

$latex a_{1}, a_{2}, a_{3} $ — целые неотрицательные числа;
$latex a_{n+3}=a_{n+1}+a_{n} $ (при $latex n = 1, 2, … $ ),

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

Решение

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

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

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

$latex 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} $

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

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

$latex 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} $.

Поэтому

$latex 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}) $.

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

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

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

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

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

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