By considering the number of $1$'s in a partition and possibly pulling a $2$ out of everything else, we get the following recurrences: \[f(2n+1)=f(2n)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(*)\] \[f(2n)=f(2n-1)+f(n)=f(2n-2)+f(n)=f(2(n-1))+f(n)~~~~~~~~~~~(**)\] \[f(2n)=f(n)+f(n-1)+\cdots+f(1)+1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(***)\] Note that while $(**)$ and $(***)$ were obtained independantly, you can derive one from the other algebraiclly. The upperbound may be obtained by using $(***)$ and induction. \begin{eqnarray*}f(2^{n+1})&=&f(2^{n})+f(2^{n}-1)+\cdots+f(1)+1\\ \ &<&\overbrace{f(2^{n})+\cdots+f(2^{n})}^{2^{n}~\mbox{\scriptsize{times}}}\\ \ &=&2^{n}f(2^{n})\\ \ &<&2^{n}\left(2^{\frac{n^{2}}{2}}\right)\\ \ &=&2^{\frac{n^{2}+2n}{2}\\ \ &<&2^{\frac{(n+1)^{2}}{2}}}\end{eqnarray*} Unfortuneately, the lower bound can't be obtained using straight forward induction like this. First we will find a crude lower bound for $(***)$, and then use induction. Note that if $f(n)$ is convex then \[f(1)+f(2)+\cdots+f(2n)>2nf(n)~~~~~~~~~~~~~~~~~~~~~~~~(****)\] And $f(n)$ is convex since $f(2(n+1))-f(2n)=f(n)\geq f(n-1)=f(2n)-f(2(n-1))$. Now we have \begin{eqnarray*}f(2^{n+1})&=&f(2^{n})+f(2^{n}-1)+\cdots+f(1)+1\\ \ &>&2^{n}f(2^{n-1})\\ \ &>&2^{n}\left(2^{\frac{(n-1)^{2}}{4}}\right)\\ \ &=&2^{\frac{n^{2}+2n+1}{4}}\\ \ &=&2^{\frac{(n+1)^{2}}{4}}\end{eqnarray*}

I'm confused. Doesn't the lower bound here contradict the result here? We should have $ f(n) \le p(n)$ if I haven't misunderstood the problem.

It appears that the question has a typo and is supposed to read $ 2^{\frac{n^2}{4}} < f(2^n) < 2^{\frac{n^2}{2}}$. At least, this is what Negative_3's solution appears to prove

Oh, wonderful. Then $ f(2^n) = [x^{2^n}] \frac{1}{(1 - x)(1 - x^2)(1 - x^4)...(1 - x^{2^{n-1}})} + 1$ and the leading polynomial term has degree $ n-1$ and leading coefficient $ \frac{1}{(n-1)! 2^{ n(n-1)/2} }$, so I would expect the asymptotic $ \frac{1}{(n-1)!} 2^{ n(n-1)/2}$, which is comfortably in-between the two given bounds although much closer to the upper bound. It should be possible from here to bound the rest of the polynomial terms as well as the periodic terms. Another thought towards a more accurate asymptotic is to let $ F(x) = \sum_{n \ge 0} f(n) x^n$ and $ P(x) = \sum_{n \ge 0} p(n) x^n$ and use the identity $ P(x) = F(x) F(x^3) F(x^5) ...$ along with the well-known asymptotic for $ p(n)$.

The typo JBL signaled is still on the main IMO resource page : http://www.mathlinks.ro/Forum/resources.php?c=1&cid=16&year=1997 Edit: Fixed by orl.

There's a very nice way of seeing that the upper limit holds: A sum $\displaystyle\sum_{i=0}^n k_i 2^i = 2^n$ can be expressed as $\displaystyle\sum_{i,j=0}^n \sigma_{ij} 2^{i+j}$, where $k_i = \displaystyle\sum_{j=0}^n \sigma_{ij}2^j$ and $\sigma_{ij} = 0$ or $1$. The value of $\sigma_{k0}$ is determined by the values of the other $\sigma_{ij}$'s with $i+j \leq k$, since $\displaystyle\sum_{i,j=0}^{i+j=k} \sigma_{ij} 2^{i+j}$ must be a multiple of $2^{k+1}$ for $k < n$. Excluding the $\sigma_{ij}$'s with $i+j=n$, there are $\dfrac {n(n-1)} 2$ bits that can be either 0 or one. So there are less than $2^{n(n-1)/2}$ partitions resulting from those bits. The partitions with $i+j=n$ add $n+1$ more partitions. So, $f(2^n) < 2^{n(n-1)/2}+n+1$, which is $\leq 2^{n^2/2}$ for $n\geq 3$. The $\sigma_{ij}$ matrix can also be used to prove the lower limit: If all the $\sigma_{ij}$'s are 1, then $\displaystyle\sum_{i,j=0}^{i+j=m} \sigma_{ij} 2^{i+j} = \sum_{k=1}^m (k+1) 2^k = m2^{m+1}$. So if $m2^{m+1}\leq 2^n$ and $\dfrac {m(m+1)} 2 > \dfrac {n^2} 4$ for some $m$, then $f(2^n) > 2^{n^2/4}$. Since $\displaystyle\lim_{m \rightarrow \infty}\dfrac {\frac {m(m+1)} 2}{(\text{log}_2(m2^{m+1}))^2} = \dfrac 1 2$, $\displaystyle\lim_{n \rightarrow \infty}f(2^n)> 2^{n^2/4}$ for large enough $n$. I think for $n\geq 16$ such $m$ can be found, but the bound would have to be checked in some other way for smaller $n$. Maybe the $\sigma_{ij}$ matrix could be used to yield a better proof for the lower bound.

Another proof for the lower bound: Consider the sums $\displaystyle\sum_{i=2}^n m_i 2^{i} = 2^n$. There are $f(2^{n-2})$ such sums, and each one can be added to a sum of the form $4k_2 + 2k_1 + k_0 = 2^n$, resulting in a distinct sum for $2^{n+1}$. There are $2^{n-1}+1$ sums of the form $2k_1 + k_0 = 2^n$, $2^{n-1}-1$ sums of the form $4 + 2k_1 + k_0 = 2^n$, $2^{n-1}-3$ sums of the form $4 + 4 + 2k_1 + k_0 = 2^n$, etc. So there are $1 + 3 + 5 + ... + (2^{n-1}+1) = (2^{n-2}+1)^2$ sums of the form $4k_2 + 2k_1 + k_0 = 2^n$. So there are more than $f(2^{n-2})(2^{n-2}+1)^2$ sums for $2^{n+1}$. $2^{(n-2)^2/4}(2^{n-2}+1)^2 > 2^{(n-2)^2/4}2^{2n-4} = 2^{(n+1)^2/4}2^{(2n-13)/4}$, which is greater than $2^{(n+1)^2/4}$ if $n\geq 7$. So, if $f(2^n)>2^{n^2/4}$ for $0 < n \leq 7$, then $f(2^n)>2^{n^2/4}$ for all $n> 0$. $f(2^3)=10 > 2^{9/4}$: Doubling the sums for 4, we get $8, 4+4, 4+2+2, 2+2+2+2$. The sum $4+2+2$ results in 2 more sums for 8, $4+2+1+1$ and $4+1+1+1+1$. Similarly, the sum $2+2+2+2$ results in 4 more sums for 8. $f(2^4) > f(2)(2+1)^2 = 18 > 2^{4^2/4} = 16$. $f(2^5) > f(4)(4+1)^2 = 100 > 2^{5^2/4}$. $f(2^6) > f(8)(8+1)^2 = 810 > 2^{6^2/4} = 512$. $f(2^7) > f(16)(16+1)^2 > 18 \times 17^2 = 5202 > 2^{7^2/4}$. So, $f(2^n)>2^{n^2/4}$ for $n> 0$.

Full solution :- There exists a bijection between representations in the given form of $2k$ and $2k+1$ for $k= 0,1,2.....$ Adding $1$ to every representation of $2k$, we get $2k+1$, and every representation of $2k+1$ contains atleast one $1$, which can be removed. So, $f(2k+1)= f(2k)$. Now consider all representations of $2k$. The number of those that contain atleast one $1$ is equal to $f(2k-1)= f(2k-2)$, while the number of those not containing a $1$ equals to $f(k)$. So, $f(2k)= f(2k-2) + f(k)$. Summing up those equations over $k=1,2,3....,n$ we get $f(2n) = f(0)+f(1)+....... +f(n)$ By applying induction, we get $f(2^{n+1})\leq 2^nf(2^n)\le 2^n2^{\frac{n^2}{2}} \le 2^{\frac{(n+1)^2}{2}}$ for each $n\ge 3$. The lower bound can be derived from the first equation. Note that the above given map $f(x+2)-f(x)$ is increasing. By recursion, for all $m,k\le m$ we have $f(2m+2k)+f(2m-2k)> 2f(2m)$. Adding all these, we obtain $f(0) + f(2) + ..... +f(4m) \ge (2m+1)f(2m)$ But $f(2)=f(3),f(4)=f(5), f(5)= f(6), f(6)= f(7) .....$ So, $f(1)+f(3)+.........+ f(4m-1)> (2m-1)f(2m)$ Combining with the above gives $f(8m)= f(0)+f(1)+........+f(4m)\ge 4mf(2m)$ Atlast we have the inequality, $f(2^n)>2^{\frac{n^2}{4}}$ and for large enough $n$ we have, $f(2^n)> 2^{n-1}f(2^{n-2})> 2^{n-1+\frac{(n-2)^2}{4}}= 2^{\frac{n^2}{4}}$ So $\boxed{2^{\frac{n^2}{4}}< f(2^n)<2^{\frac{n^2}{2}}}$

From Twitch Solves ISL: It's clear that $f$ is non-decreasing. By sorting by the number of $1$'s we used, we have the equation \[ f(N) = f\left( \left\lfloor \frac N2 \right\rfloor \right) + f\left( \left\lfloor \frac N2 \right\rfloor -1 \right) + f\left( \left\lfloor \frac N2 \right\rfloor -2 \right) + \dots + f(1) + f(0). \quad (\bigstar) \]Upper bound. We now prove the upper bound by induction. Indeed, the base case is trivial and for the inductive step we simply use $(\bigstar)$: \[ f(2^n) = f(2^{n-1}) + f(2^{n-1}-1) + \dots < 2^{n-1} f(2^{n-1}) < 2^{n-1} \cdot 2^{\frac{(n-1)^2}{2}} = 2^{\frac{n^2}{2} - \frac{1}{2}}. \]Lower bound. First, we contend that $f$ is convex. We'll first prove this in the even case to save ourselves some annoyance: Claim: [$f$ is basically convex] If $2 \mid a+b$ then we have $f(2a) + f(2b) \ge 2 f\left( a+b \right)$. Proof. Since $f(2k+1) = f(2k)$, we will only prove the first equation. Assume WLOG $a \ge b$ and use $(\bigstar)$ on all three $f$ expressions here; after subtracting repeated terms, the inequality then rewrites as \[ \sum_{(a+b)/2 \le x \le a} f(x) \ge \sum_{b \le x \le (a+b)/2} f(x). \]This is true since there are an equal number of terms on each side and $f$ is nondecreasing. $\blacksquare$ Claim: For each $1 \le k < 2^{n-1}$, we have \[ f(2^{n-1} - k) + f(k+1) \ge 2f(2^{n-2}) \]Proof. Use the fact that $f(2t+1)=f(2t)$ for all $t$ and then apply convexity as above. $\blacksquare$ Now we can carry out the induction: \[ f(2^n) = f(2^{n-1}) + f(2^{n-1}-1) + \dots > 2^{n-1} f(2^{n-2}) + f(0) > 2^{n-1} 2^{\frac{(n-2)^2}{4}} = 2^{\frac{n^2}{4}}. \]

Observe that $f(2n) = f(2n+1)$ for all $n$. First, we have the recursion $$f(n) = f(1) + f(2) +\cdots + f(\lfloor n/2 \rfloor)$$for all $n$ by considering possible groupings of $1$'s in the representation of $n$. In particular, starting from $n = 1+1+\cdots + 1$, we may group any $k \leq \lfloor n/2 \rfloor$ groups of two $1$'s into $k$ $2$'s. We then equivalently must construct a partition for $k$; the remaining $1$'s cannot be used by definition of the grouping. Now this becomes routine bounding. Notice first that $$f(2^n) = f(1)+f(2)+\cdots+f(2^{n-1}) < 2^{n-1} f(2^{n-1}),$$so multiplying recursively yields $$f(2^n) < 2^{n-1} \cdot 2^{n-2} \cdots 2^1 \cdot 2^0 = 2^{n(n-1)/2} < 2^{n^2/2}.$$On the other hand, observe that $f$ is essentially convex because $f(2a)+f(2b) \geq 2f(a+b)$ for all $f$ (simply by expanding each term and noticing that $f$ is nondecreasing). Hence we also have $$f(2^n) = f(1)+f(2)+\cdots+f(2^{n-1}) > 2^{n-1} f(2^{n-2}).$$Iterating this yields $f(2^n) > 2^{n^2/4}$, as needed.

The main idea is that \[f(2n)=\sum_{i=0}^nf(i)\]and $f(2n+1)=f(2n)$ where we define $f(0)=1.$ The first is by removing all $1$s in a representation and dividing by $2.$ The second is clear by parity. Now we can manually check $f(8)$ and $f(16)$ work and then we just want to show $2nf(n)\le f(4n)\le 4n^2f(n)$ for $n\ge 8$ and induction would finish. First we show the lower bound. The first step is that $f$ is clearly nondecreasing. Next, note that when $m\ge n$ we have \[f(2m)-f(2m-1)=\sum_{i=0}^mf(i)-\sum_{i=0}^{m-1}f(i)=f(m)\ge f(n)=\sum_{i=0}^nf(i)-\sum_{i=0}^{n-1}f(i)=f(2n)-f(2n-1).\]Additionally it holds that $f(2m+1)-f(2m)=0=f(2n+1)-f(2n).$ In other words, $f$ is "convex-ish": for fixed odd $n$ and varying $x,y$ with $x+y=n,$ the sum $f(x)+f(y)$ is maximized when $x,y$ are closest together. Now write $f(4n)=1+f(1)+f(2)+\dots+f(2n),$ and we can pair together opposite terms to get $f(4n)\ge 1+nf(n)+nf(n+1)\ge 2nf(n)$ as desired. For the upper bound just write \[f(4n)=f(0)+f(1)+\dots+f(2n)=(2n+1)f(0)+(2n-1)f(1)+(2n-3)f(2)+\dots+f(n)\le f(n)(1+3+\dots+2n+1)=(n+1)^2f(n)\le 4n^2f(n)\]so we are done.