38-я Международная Математическая OлимпиадаАргентина, Мар-дель-Плата, 1997 год

Для каждого натурального $n$ через $f\left( n \right)$ обозначим количество различных представлений числа $n$ в виде суммы степеней двойки с целыми неотрицательными показателями. (Представления, отличающиеся только порядком слагаемых, считаются одинаковыми.) Например, $f\left( 4 \right)=4$, так как число 4 может быть представлено следующими четырьмя способами: $4$; $2+2$; $2+1+1$; $1+1+1+1$. Докажите, что для любого натурального $n\ge 3$ выполнено неравенство $${{2}^{\dfrac{{{n}^{2}}}{4}}} < f\left( {{2}^{n}} \right) < {{2}^{\dfrac{{{n}^{2}}}{2}}}.$$