Here is a proof of the lower bound of 13:
![enter image description here](https://cdn.statically.io/img/i.sstatic.net/aPCiV.png)
There are thirteen more red cells than blue cells (69 red and 56 blue), but each rectangle with sides that are powers of two can contain at most one more red cell than blue cell. Therefore, it would take 13 rectangles to tile the whole grid.
Why it works (and how I found it):
First, I started with a simple 1x15 array of numbers:
. This array sums to 4. Every rectangle of numbers with power-of-2 sides sums to at most 1, and negative sums arise with a rectangle consisting of a single negative cell or a rectangle with two cells containing the -2.
I then multiplied the array by itself, creating this array:
.
This new array sums to 16, and the only problematic rectangles with a sum of more than 1 are those created by multiplying a negative-summing rectangle with the square containing -2.
To fix the two-cell rectangles, I reduced the 4 in the middle to a 2. The sum became 14. All the multi-cell rectangles containing the center have a non-positive sum.
I then colored the squares like a checkerboard with white corners, reduced all the white squares by 1, and increased all the black squares by 1. This dealt with all the problematic single-cell rectangles while not affecting the sums of the rectangles with an even number of cells. The sum of the whole array became 13.
Once this array contained only 1s, 0s, and -1s, I removed the numbers and added colors.
Because all the multi-cell rectangles containing the center have a nonpositive sum, the only way to cover the center in a 13-rectangle tiling is with a 1x1 square.