Этюд о рекуррентных соотношениях

Мы демонстрируем важный метод работы с рекуррентными соотношениями на простых примерах его применения (§ 1). Один из них — «олимпиадная» задача (утверждение 1), возникшая из новой оригинальной детали в доказательстве локальной леммы Ловаса (§ 2). Мы приводим несколько определений и формулировок, поясняющих метод разложения многочлена от оператора сдвига, вместе со ссылками на более подробное изложение (§ 3). Формально § 3 не использует предыдущие параграфы, поэтому чтение заметки можно начинать и с него. Но лучший способ познакомиться с методом — разобрать простые примеры его применения (§ 1).