KöMaL 2018 A715

Let $a$ and $b$ be positive integers. We tile a rectangle with dimensions $a$ and $b$ using squares whose side-length is a power of $2$, i.e. the tiling may include squares of dimensions $1\times 1$, $2\times 2$, $4\times 4$ etc. Denote by $M$ the minimal number of squares in such a tiling. Numbers $a$ and $b$ can be uniquely represented as the sum of distinct powers of $2$: $a=2^{a_1}+\cdots+2^{a_k}$, $b=2^{b_1}+\cdots +2^{b_\ell}$. Show that $M=\sum_{i=1}^k \;\sum_{j=1}^{\ell} 2^{|a_i-b_j|}.$