Очень логично было бы доказывать, например, неравенство экспоненциального роста:
L_{n+1} >= c*L_n,
где c>1 — какая-то (хорошо выбранная) константа. Разумеется, доказывать — по индукции.
Потому что если L_n экспоненциально растёт, то вычитаемые L_{n+1-k} должны оказываться «маленькими» по сравнению с уже имеющимся L_n.
И действительно: если у нас L_m >= c L_{m-1} при m<=n, то
L_{n+1-k} <= L_n / c^{k-1}, откуда
L_{n+1} >= 2 L_n - \sum_{k>=5} L_{n+1-k}
>= 2 L_n - \sum_{k>=5} L_n /c^{k-1} =
(2- \sum_{r>=4} c^{-r} ) L_n.
Значит, для доказательства остаётся найти такое c на отрезке от 1 до 2, что
2- \sum_{r>=4} c^{-r} >= c.
Если такое есть — всё доказано.
Post #4462
2.85K