Сколько программ исполнителя «прибавь 1, умножь на 3» переводят число 2 в число 22

Решение по шагам

1. 1

   Шаг 1. Заводим функцию «сколько программ ведёт в число n»

   Прямой перебор всех последовательностей команд неудобен: программы бывают разной длины. Вместо этого посчитаем задачу «снизу вверх».

   Обозначим через $R(n)$ количество программ, переводящих стартовое число 2 в число $n$.

   База: $R(2) = 1$ — это «пустая» программа, ничего делать не надо. Такое соглашение удобно: оно не портит ответ, потому что до числа 22 всё равно придётся выполнить хотя бы одну команду.

   Важное наблюдение: обе команды только увеличивают число. Значит, все промежуточные значения лежат между 2 и 22, а до чисел меньше 2 добраться нельзя, поэтому $R(n) = 0$ при $n < 2$.

2. 2

   Шаг 2. Выводим рекуррентную формулу

   Посмотрим на последнюю команду программы, которая привела нас в число $n$. Вариантов ровно два.

   1. Последней была «прибавь 1». Тогда до неё на экране стояло $n-1$, а способов туда попасть — $R(n-1)$.
   2. Последней была «умножь на 3». Это возможно, только если $n$ делится на 3; тогда до неё на экране стояло $n/3$, а способов — $R(n/3)$.

   Варианты не пересекаются, поэтому их количества складываются:

   $$R(n) = R(n-1) + \begin{cases} R(n/3), & n \text{ кратно } 3,\\ 0, & \text{иначе.}\end{cases}$$

   Остаётся аккуратно заполнить таблицу от 2 до 22, не забывая, что $R(n)=0$ для $n<2$.