Азиатско-Тихоокеанская математическая олимпиада, 2017 год
Комментарий/решение:
Пусть $\mathrm{S}=\{2^m-1\mid \forall m\in\mathbb N\}$
Тогда $A(n)$ равно количеству способов представить число $n$ в виде суммы элементов из $\mathrm S.$ (элементы из $\mathrm S$ можно использовать насколько раз.)
Построим биекцию $(b_1,\ldots,b_m)\longleftrightarrow (x_1,\ldots,x_m):$
$1) b_m=x_m$
$2) b_i-2b_{i+1}=x_i,\forall i=1,\ldots,m-1;$
Из условия $x_i\in\mathbb{Z_{\ge 0}}$ и $\{ x_1,\ldots,x_m\}\ne\{0,\ldots,0 \}.$ Тогда $$\large{n=\sum\limits_{i=1}^{m} b_i=\sum\limits_{i=1}^{m}}(2^i-1)\cdot x_i$$
Пусть $X(n)$ равно количеству последовательностей $(x_1,\ldots, x_m)$ таких, что $$\large{n=\sum\limits_{i=1}^{m}(2^i-1)\cdot x_i,\quad x_i\ge 0} $$
Из ранее показаной биекции следует, что $X(n)=B(n).$ Так же очевидно, что $X(n)$ равно количеству способов представить число $n$ в виде суммы элементов из $\mathrm S.$ Откуда $A(n)=X(n).$
Значит $A(n)=B(n).$
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.