# Regular languages: Prove $2^n + n < 2^{n+1}$ for $n \ge 1$

I was trying to use the pumping lemma to prove that the language, $\{ 0^N | \ n$ is a power of 2$\}$, is not regular.

Assume to the contrary that the language is regular. Let p be the pumping length given by the pumping lemma and let $s = 0^{2^p}$. As $|s| \ge p$, the pumping lemma guarantees we can split s into three pieces $x, y, z$ such that $y \ne$ empty string, $|xy| \le p$ and $xy^iz \in$ the language.

From the conditions of the pumping lemma, we know y contains between one and $p$ zeros. In the case that $i=2$, the length of $xyyz$ is between $0^{2^p} + 1$ and $0^{2^p} + p$. However, to get to the next power of 2 after $0^{2^p}$, we need $0^{2^p + 1}$.

I wanted to prove the bounds of $|xyyz|$ are less than the $0^{2^{n+1}}$. To do this I began writing an inductive proof to show that $0^{2^n} + n < 0^{2^{n+1}}$ for $n \ge 1$.

Basis: $n=1$

$0^{2^1} + 1 \rightarrow$ length is $3$

$0^{2^{1 + 1}} \rightarrow 0^{2^2} \rightarrow$ length is $4$

Induction: assume the statement is true for all $n \le k$. Lets do the case for $n = k + 1$

$0^{2^{k+1}} + k + 1 = 0^{2^k \cdot 2} + k + 1$

$0^{2^{k + 1 +1}} = 0^{2^k \cdot 2 \cdot 2}$

This is where I get stuck. I can see very clearly that $0^{2^k \cdot 2 \cdot 2}$ is greater than $0^{2^{k+1}}$, but I don't see how its greater than $0^{2^{k+1}} + k + 1$

• Off-topic: When I saw the title I thought "Oh my lord that guy wrote $0^{2^n}$ and $0^{2^{n+1}}$ in a inequation, it's nonsense", and then when I entered I realized what he was up to. Commented Apr 18, 2018 at 0:35
• @manooooh good point, I'll edit the title Commented Apr 18, 2018 at 0:45
• I take it that by O you actually mean $\mathcal{O}$ Commented Apr 18, 2018 at 1:22

First of all, "I began writing an inductive proof to show that $0^{2^n} + n < 0^{2^{n+1}}$ for $n≥1$" is definitely inaccurate since you can't add a string to a number. You are trying to show the length of string satisfies that condition, as your title said.
Then you only need to prove $2^n > n$, which can be easily solved by calculus or induction. Anyway, the problem in your proof is that you didn't focus on string's length.