The Tu--Deng Conjecture holds almost surely

The Tu–Deng Conjecture is concerned with the sum of digits $w(n)$ of $n$ in base~$2$ (the Hamming weight of the binary expansion of $n$) and states the following: assume that $k$ is a positive integer and $1\le t<2^k-1$. Then $$\mid \{(a,b)\in \{0,\dots ,2^k-2{\}}^2:a+b\equiv t{2}^k-1,w(a)+w(b)<k\}\mid \le 2^{k-1}\mathrm{.}$$ We prove that the Tu–Deng Conjecture holds almost surely in the following sense: the proportion of $t\in [1,2^k-2]$ such that the above inequality holds approaches $1$ as $k\to \mathrm{\infty }$. Moreover, we prove that the Tu–Deng Conjecture implies a conjecture due to T.~W.~Cusick concerning the sum of digits of $n$ and $n+t$.