Return to Answer

In contrast, it is the converse question that I find extremely interesting. Namely,

Theorem. If $T\subset 2^{<\omega}$ is a binary tree with growth rate $\Omega(2^n)$ (in the Knuth sense Big-Omega notation), then $T$ has continuum many branches.

Theorem. If $f:\mathbb{N}\to\mathbb{N}$ is $o(2^n)$ (see Little-o notation), then there is a tree $T$ with growth rate exceeding $f$, but having only countably many paths.

In contrast, it is the converse question that I find extremely interesting, and which could be considered the real content of your question. Namely,

Theorem. If $T\subset 2^{<\omega}$ is a binary tree with growth rate $\Omega(2^n)$ (in the Knuth sense big-Omega notation), then $T$ has continuum many branches.

Theorem. If $f:\mathbb{N}\to\mathbb{N}$ is in $o(2^n)$ (see little-o notation), then there is a tree $T$ with growth rate exceeding $f$, but having only countably many paths.

Proof. We build $T$ in stages. First, we let $T$ use the full binary branching up to some level $n_0$. Then, at this stage, we allow only half of the nodes to branch, the ones that started out with $1$ in the their first bit, and force the other half, the ones beginning with $0$, to become isolated branches in the tree starting at level $n_0$, continued only with more $0$s after $n_0$. Meanwhile, we let the other "live" nodes, beginning with $1$, to continue splitting above $n_0$ until some much larger stage $n_1$. At that level, we again kill off half of them. Namely, any node beginning with $10$ will become isolated at $n_1$, and the others will continue splitting up until the very much later stage $n_2$. And so on.

Proof. The growth rate assumption is that for every $r>0$, it will be true for large enough $n$ that $f(n)<r2^n$.

Let me describe a general procedure for building a tree $T$ with a very high growth rate, but with only countably many branches. We build $T$ in stages. First, we let $T$ use the full binary branching up to some level $n_0$. Then, at this stage, we kill off the future growth of half the branches, the ones beginning with $0$, forcing them to become isolated branches in the tree starting at level $n_0$, continued only with more $0$s after $n_0$. Meanwhile, we let the other "live" nodes, those having $1$ in their first bit, to continue splitting above $n_0$ until some much larger stage $n_1$. At that level, we again kill off half of them. Namely, any node beginning with $10$ will become isolated at $n_1$, and the others, beginning with $11$, will continue splitting up until the very much later stage $n_2$. And so on.

But now, the main point, is that by choosing the levels $n_0<n_1<n_2<\cdots$ to be very fast growing, we can ensure a growth rate exceeding $f$. Specifically, since $f$ is $o(2^n)$, there is for each $k$ a number $n_k$ such that $f(n))<2^{n-k}$ for all $n\geq n_k$, and we may also assume $n_0<n_1<n_2<\cdots$. Now, with the $T$ as defined above, it follows that the number of nodes of $T$ on level $n_k$ is at least $2^{n_k-k}$, and it remains at least $2^{n-k}$ for $n_k\leq n<n_{k+1}$, and this is larger than $f(n)$, as desired. So the growth rate of $T$ is at least $f$, even though $T$ has only countably many paths. QED

But now, the main point, is that by choosing the levels $n_0<n_1<n_2<\cdots$ to be very fast growing, we can ensure a growth rate exceeding $f$. Specifically, since $f$ is $o(2^n)$, there is for each $k$ a number $n_k$ such that $f(n)<2^{n-k}$ for all $n\geq n_k$, and we may also assume $n_0<n_1<n_2<\cdots$. Now, with the $T$ as defined above, it follows that the number of nodes of $T$ on level $n_k$ is at least $2^{n_k-k}$, and it remains at least $2^{n-k}$ for $n_k\leq n<n_{k+1}$, and this is larger than $f(n)$, as desired. So the growth rate of $T$ is at least $f$, even though $T$ has only countably many paths. QED