The sum above is $\approx \sqrt{2^{2^{2k}}}$ so, rel$(A,B)$ becomes $\frac{3}{4}$. (assuming $k$ starts with $0$). I have been convinced. Thank you!

I assume no inclusion. So, $A$ and $B$ are related only via the relative density. Maybe, it would be good to start with a subset and prove that A would be a thinner asymptotic basis. One obvious case is when A is a superset of B and we don't even need density..