Tiling a square with rectangles Consider the set of all the rectangles with dimensions $2^a\times 2^b\,a,b\in \mathbb{Z}^{\ge 0}$. We want to tile an $n\times n$ square by rectangles from this set (you can use a rectangle several times). What is the minimum number of rectangles we need?
If $f(n)$ is the sum of digits of $n$ in base $2$, I think we need at most $f(n)^2$ rectangles. I have an example for this number: write $n=2^{a_1}+2^{a_2}+...2^{a_{f(n)}}$ and split each side to segments with length $2^{a_1},2^{a_2},...,2^{a_{f(n)}}$ and consider $f(n)^2$ rectangles obtained this way.
On the other hand, you need at least $f(n)$ rectangles to tile a raw (or column) so I think you need $f(n)^2$ rectangles, but I can't prove it.
Any ideas? 
 A: NOTE:This doesn't work, the induction hypothesis is too strong (and false).
Lets first consider a more general question, where we tile a rectangle $R$ by smaller rectangles, where all vertices are points in an (ambient) integer lattice.
We have a row of rectangles $T_i$ touching the bottom edge of $R$, and each of these has a top edge $e_i$. For each $T_i$ we define the number $\lambda(T_i)$ to be the minimal number of our tiling rectangles that intersect any column starting in $T_i$.
Our first claim is that for the total number of rectangles in $R$, denoted $r(R)$, we have $$\sum_i \lambda(T_i) \leq r(R)$$
Lets prove this by induction on the height of the rectangle $R$ (drawing a picture may help see whats happening). First, if the height is $1$, then we are done trivially.
So now for the inductive step, let $R_0$ have height $n$, and consider the edges $e_i$ that have minimal height, and define $a$ to be this height. This is to say, they border the $a$th row, if the first row is the bottom row of $R_0$. Say that we have $k$ minimal edges $e_i$ bordering this row.
We now consider the new rectangle $R_0'$ we obtain by chopping off the first $a$ rows of $R$. On one hand, this has strictly smaller height, so we have, by induction and our definition of $k$: $$\sum_i \lambda(T_i') \leq r(R_0)-k$$
But each rectangle on the bottom row of $R_0'$ is either one of the rectangles of $R_0$, chopped, but not removed, or a rectangle of $R_0$ lying above one of our minimal edges $e_i$.
Now note if our original $T_i$ is chopped but not removed, $\lambda(T_i)=\lambda(T_i')$, and if our original $T_j$ is removed (so top edge has minimal height), then $\lambda(T_j')=\lambda(T_j)-1$, where $T_j'$ is any of the rectangles lying directly over $T_j$. Thus, adding $k$ to both sides of our previous equality, we have:
$$\sum_i \lambda(T_i) \leq \sum_i \lambda(T_i')+k\leq r(R_0)$$
So we are done by induction.
So for your case, note that each column must have at least $f(n)$ rectangles in it, and note the bottom row has at least $f(n)$ rectangles. This follows since $f(n)$ is the minimal number of powers of two needed to express $n$. Thus, $f(n)^2\leq r(R)$ in your case.
