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][1]  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.

  [1]: https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem#Algebraic_graph_theory