Кто сказал "подстановочные слова"? 🙂

Через несколько минут!

последняя лекция ЛШСМ-2021: Андрей Окуньков расскажет про q-аналоги и кратные дзета-значения — 29.07 в 15:30 будет прямая трансляция, https://youtu.be/EMaHG4VUflc

Продолжим? Так вот, если написать начало такой последовательности, то получается
21 211 21 21 211 21 211 21 21 211 21 211 21 211 21 21 211 21 211 21 21 211 21 211 21 21 211 21 211 21 211 21 21 211 21 211 21 21 211 21 211 ...
(я добавил пробел перед каждой двойкой)

Если заменить 21 на единицу, а 211 на двойку, то получается
1 211 21 211 21 21 211 21 211 21 211 21 21 211 21 211 21 2...

Если выкинуть первую единицу, и дальше (опять!) заменить каждую 21 на единицу, а 211 на двойку, то получается
21 211 21 21 211 21 211 21 21 211 ...

Иии — это буквально та последовательность, которую мы только что видели!

А такая (получающаяся итерированием подстановок) последовательность должна кодироваться поворотом окружности: берём поворот R на какой-то угол \theta, отмечаем дугу I=[0,\theta), и выбираем начальную точку x_0. И пишем один символ (например, "2"), если очередной образ R^n(x_0) попадает на дугу I, и другой (например, "0"), если не попадает.
Тогда подстановки приходят из идеи отображения первого возвращения на дугу I. А именно, для каждой точки x с этой дуги можно посмотреть, когда она в следующий раз вернётся на I — будет некоторая точка T(x), — и сгруппировать символы до момента возвращения.
Тогда дуга I поделится на две поддуги, на одной из которых мы будем читать 2+(сколько-то 1), а на другой — 2+(на одну 1 больше). А если склеить дугу I в окружность — то отображение T оказывается опять её поворотом — на другой угол \theta'.
Называются так получающиеся слова словами (или последовательностями) Штурма; кстати — там есть хорошая анимация:
https://en.wikipedia.org/wiki/File:Sturmian-sequence-from-irrational-rotation.gif
Собственно — буквально то, что мы раньше обсуждали для слова Фибоначчи!

Угол \theta в нашем случае несложно найти — на дугу длины \theta (на окружности длины 1) попадает при иррациональном повороте примерно такая же доля итераций (потому что орбиты распределяются примерно в соответствии с мерой Лебега). Но мы знаем, как устроена эта доля: от 1 до N^2 будет примерно \sqrt{2}*N треугольных чисел, так что доля "двоек" в нашей последовательности стремится к (sqrt{2}-1). Поэтому
\theta=\sqrt{2}-1.

Нужно ещё найти начальную точку — именно из-за неё последовательность в себя переходит не за один шаг замен, а за два (собственно, могла и бы и вообще буквально в себя не переходить: разных вариантов выбора начальной точки континуум, а переходящих буквально в себя, даже со сдвигом, подстановочных последовательностей лишь счётное число).

И тут я предпочту показать дорогу к ответу, и сам ответ, а "поимку ручного льва" предоставить читателям.

Дорога к ответу, собственно, очень простая: если сравнивать k-е треугольное число с n-м квадратом, то мы сравниваем
k(k+1)/2 и n^2,
или, что то же самое,
(k+ 1/2)^2 и 2n^2 + (1/4).
Но (1/4) на нестрогое неравенство ">=" влияния не окажет (потому что левая часть всегда имеет дробную часть (1/4)). А тогда мы сравниваем
(k+ 1/2) с \sqrt{2}*n.
Вот у нас и появился корень из 2 и сдвиг на (1/2) — и квадратные и треугольные числа идут в таком же порядке, как пересечения с горизонтальными (y=k) и вертикальными (x=n) прямыми у прямой
y+1/2=sqrt(2)*x.

И тут мне хочется вспомнить картинку из статьи Концевича "Равномерные расположения" в "Кванте" (1985 год, N7) — посмотрите на задачу номер 5* и на рис. 8.

Ну а при переходе от "в каком порядке числа из двух последовательностей идут" к "сколько одних между другими" всё чуть-чуть поменяется, и вот последовательность Штурма, построенная по углу \theta=\sqrt{2}-1 и с начальной точкой
x_0 = 2\theta - 0.5 :
21 211 21 21 211 21 211 21 21 211 21 211 21 211 21 21 211 21 211 21 21 211 21 211 21 21 211 21 211 21 211 21 21 211 21 211 ...

Кстати — то, что последовательность замен одна и та же, соответствует тому, что цепная дробь для корня из двух периодична:

Как положено, за фотографией "с чего всё начиналось" должны следовать "что было дальше" и "как всё закончилось". Первая:

Вторая:

Тут происходит уход в совсем другую науку (спектры операторов) — которая очень красиво связана с первой!

Давайте теперь я чуть-чуть поговорю про вторую половину.
Если линейное преобразование переводит вектор в пропорциональный себе, то такой вектор называется собственным вектором, а коэффициент пропорциональности — собственным значением.
Есть очень хорошее видео 3blue1brown про эти понятия —
https://www.youtube.com/watch?v=PFDu9oVAE-g
Собственно, то, что числа Фибоначчи растут как c*φˆn, связано с тем, что φ — наибольшее собственное значение матрицы
(1 1)
(1 0),
применение которой соответствует сдвигу "окна наблюдения" в последовательности Фибоначчи: она переводит вектор (F_n, F_{n-1}) в (F_{n+1},F_n).
А набор собственных значений конечной матрицы называется её спектром.

Ну и слово "спектр" тут вполне себе физически мотивировано. Мы тут недавно как раз вспоминали спектр атома — как раз допустимые для электрона уровни энергии являются собственными значениями соответствующего оператора (Шрёдингера или Дирака) из квантовой механики. А при перепрыгивании электрона с более высокого энергетического уровня на более частота излучаемого фотона соответствует (E=hν) разности энергий — так что вот мы и видим "серию полосок" в спектре (точнее, сразу много серий — потому что всевозможные попарные разности — но заметём это под ковёр!).

+ картинка из Википедии:
https://commons.wikimedia.org/wiki/File:Hydrogen_spectrum.noscript

В бесконечномерных пространствах, правда, всё становится заметно сложнее. И вторая часть лекции началась с рассмотрения пространства бесконечных в обе стороны последовательностей, и оператора H, заданного вот такой (бесконечной в обе стороны) матрицей (она видна посередине этой доски) —

Собственно, этот оператор — чуть-чуть подправленная дискретная версия одномерного оператора Лапласа: вместо второй производной взято второе приращение
(f_{n+1}-f_n) - (f_n-f_{n-1}) = (f_{n+1}+f_{n-1}) - 2f_n,
из которого часть "-2*f_n", умножение функции на (-2), убрали (что на собственные вектора не влияет, а все собственные значения должно было увеличить на 2).

Если брать буквально всё пространство последовательностей — то оно "слишком большое" и не нормированное. Поэтому правильно рассматривать пространство l_2 последовательностей со сходящейся суммой квадратов модулей. В котором есть естественное скалярное произведение,
<f,g>= \sum_n f_n \bar{g}_n,
и порождённое им расстояние: длина вектора это корень из его скалярного квадрата
|f|^2 = \sum_n |f_n|^2.
Кстати, если у нас есть единичный по длине вектор \psi, а оператор мы рассматриваем как пришедший из квантовой механики — то |\psi_n|^2 можно интерпретировать как вероятность того, что при измерении частица окажется в точке n. Как раз получаются неотрицательные числа с суммой 1.

А что у H с собственными векторами? [Тут чуть-чуть отклонюсь от хода лекции и добавлю отсебятины]
Если бы нас интересовали просто последовательности, без всяких условий — то подошли бы любые геометрические прогрессии r^n.

Это и логично: наш оператор коммутирует с оператором "сдвига всей последовательности влево", поэтому логично искать у них общие собственные вектора — а у сдвига влево собственный вектор с собственным значением r это как раз геометрическая прогрессия со знаменателем r.

Но они нам не подходят. Скажем, если |r|>1, то такая последовательность экспоненциально возрастает при сдвиге вправо, а если |r|<1 — при сдвиге влево. И это уж совсем ни в какие ворота.
Увы, последовательности с |r|=1 тоже буквально в нашем пространстве не лежат — хоть они по модулю не растут, но и не убывают. Поэтому настоящих собственных векторов у H нет.

//putting my physicist hat on//
Но (я не буду придавать этому кусочку аккуратный смысл, байка есть байка) — есть обобщённые: геометрические прогрессии
(F_{\alpha})_n=e^{2πi \alpha n},
где \alpha из окружности R/Z, с единичным по модулю знаменателем
r=e^{2πi \alpha}
(собственно, принадлежащим окружности |r|=1 на комплексной плоскости).

Они, конечно, не принадлежат пространству l_2 — ряд из квадратов модулей это ряд из одних единиц — но давайте мы это сейчас проигнорируем.

Тогда можно разложить функцию f по такому "базису" — сопоставив каждой точке \alpha окружности R/Z соответствующий коэффициент-"скалярное произведение"
u(\alpha) = \sum_n f_n e^{-2πi \alpha n}.

На самом деле — мы только что придумали заново ряд Фурье! (Правда, у нас в итоге минус перед \alpha оказался не там, но это не так важно.)
Потому что в обратную сторону мы возвращаемся интегралом
f_n = \int_0^1 u(\alpha) (F_{\alpha})_n d\alpha =
\int_0^1 u(\alpha) e^{2πi \alpha n} d\alpha.
Так что последовательность f — это (с точностью до замены n на -n или \alpha на -\alpha) последовательность комплексных коэффициентов Фурье функции u на единичной окружности.

(Правда, я тут пару раз сжульничал, один раз, когда забыл нормировать коэффициент на [бесконечную] норму базисного вектора, а второй, когда сумму по базисным векторам заменил на интеграл. Так вот — эти два жульничества отменяют друг друга, и всё в итоге получается правильно.)