You could show that it is one of $r$ approximately equal things which add to $2^n.$ You might also bound how far apart they can be from each other. This is really pretty much what Fedor said but the details are fun.
Fix $r,$ mark $r$ equally spaced positions (numbered $0$ to $r-1$) on a circle and consider a particle which starts at time $0$ at position $0$. At time $n+1$ the particle either stays where it was at time $n$ (say position $j$) or else moves to position $j+1$ (considered $\bmod n.$) These two possibilities each happen with probability of $\frac12.$
If $p_j(n)$ is the probability of being at site $j$ at time $n$ then $$p_j(n+1)=\frac{p_j(n)+p_{j-1}(n)}2.$$ Of course the probabilities $\sum p_j(n)=1$ and clearly, due to the averaging, as $n$ grows they approach equality: $p_j(n) \rightarrow \frac1r.$
If we define $S_j(n)=2^np_j(n)$ then we have the recurrence $$S_j(n+1)=S_j(n)+S_{j-1}(n).$$
It is easy to see that in fact $$S_j(n)=\sum_{k \ge 0}\binom{m}{rk+j}.$$ So they all approach $\frac{2^n}{r}.$
The clearly seems pretty obvious and we are pretty familiar with the fact that any appropriate random walk on a graph approaches a stationary distribution (by appropriate one might mean a non-zero probability of staying in the same place to avoid periodic behavior.) A proof might deal with Perron eigenvector associated with the dominant eigenvalue of the transition matrix. In this case the eigenvalues are the $1+\omega^j$ and the dominant one is $2$ (for $j=0$) with eigenvector having all entries equal.