Оценка мощности одного множества

[Lion]

Возникла следующая забавная задача.

Рассмотрим набор натуральных чисел (среди которых, возможно, есть совпадающие). С ним производится следующая процедура: ко всем числам прибавляем 1 и отнимаем 1. Из полученного множества убираем нули (если есть) и повторяем процедуру. На каждом шаге могут возникать совпадающие числа, их всегда считаем отдельно.
Пусть мы стартовали с множества, состоящего из числа 1, т.е. последовательность такая: (1), (2), (1, 3), (2, 2, 4), (1, 3, 1, 3, 3, 5) и т.д. Мощность множества, возникающего на $k$-м шаге, обозначим через $N_k$.
Вопрос: чему равно $N_k$?

Снизу $N_k$ оценивается $k$-м числом Фиббоначчи, а сверху --- $2^{k-1}$, т.е. между двух экспонент. Хотелось бы уточнить верхнюю оценку, точнее, получить оценку сверху вида $AB^{k}$, где $B<2$.

Пока никак не получается...

[ИСН]

Это что-то простое, вроде как средний биномиальный коэффициент. Переформулируйте в терминах случайных блужданий, там должно стать видно.

[Руст]

Да, здесь на форуме как то явно выражали это. Ясно, что цель $B<2$ не осуществимо, так как порядок роста порядка $\frac{2^n}{n^a}$ a=1 или 1/2.

[maxal]

Справедлива простая формула:

$$N_k = \binom{k-1}{\lfloor(k-1)/2\rfloor}.$$

Доказательство тут: http://www.artofproblemsolving.com/Foru ... 41&t=58575