Question

Интересная задачка...
Только вот как это доказать

Answer 1

Пусть известно число $a_{k}$, оценим $a_{k+1}$. Тогда достаточно выкинуть из всевозможных слов длины $k+1$ слова, начинающиеся со слов длины $k, k-1, \;..., \; 1$ (таковых $a_{k}n+a_{k-1}n^2+...+a_{1}n^k$), то есть $a_{k+1}\leq n^{k+1}-(a_{k}n+a_{k-1}n^2+...+a_{1}n^k) \Rightarrow \frac{a_{k+1}}{n^{k+1}}\leq 1-\sum\limits_{j=1}^{k}\frac{a_{j}}{n^{j}}$. Отсюда $\sum\limits_{j=1}^{\infty}\frac{a_{j}}{n^{j}}=\lim\limits_{k\to\infty} \sum\limits_{j=1}^{k}\frac{a_{j}}{n^{j}}=\lim\limits_{k\to\infty}(1-\frac{a_{k+1}}{n^{k+1}})\leq 1$, поскольку очевидно, что $\frac{a_{k+1}}{n^{k+1}}\leq 1 \;, \forall k$, ведь максимальное число слов длины $t$ есть число $n^t$