IMO олимпиада по математике 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}}}.$