Why is the minimum size of a generating set for a finite group at most $\log_2 n$?
Solution 1:
If $G$ is a finite group, and $\{g_1,\ldots,g_m\}$ is a minimal set of generators, let $G_n = \langle g_1,\ldots,g_n \rangle$. Then by minimality $g_k \ne e$ for all $k$, and $g_{n+1} \notin G_n$ for all $n$. Then $G_{n+1}$ contains at least the two disjoint cosets $eG_n=G_n$ and $g_{n+1}G_n$ of $G_n$, so $|G_{n+1}| \ge 2|G_n|$. By induction $|G| = |G_m| \ge 2^m$, so $m \le \log_2 |G|$. This inequality is sharp for $G = \mathbb{Z}_2^m$.