It's enough to prove that being at the point $x$ at its $k$-th move, the flea can make some jumps and after that to reach $x\pm 1$. Indeed, let it jumps $m+1$ times to the right and the last $m+2$-th jump be to the left. Thus it would be at the point: \[x+(2^{k}+1)+(2^{k+1}+1)+\dots +(2^{k+m}+1) - (2^{k+m+1}+1)=x-2^{k}+m.\]Now, choosing $m=2^k\pm 1$, we prove the claim.

I claim it is possible. Lemma: Given any $k\in \mathbb{N}$, there exists some $n>k$ such that \[ (2^k+1)+(2^{k+1}+1)+\cdots+(2^{n-1}+1) - (2^n+1) = 1.\]Proof: Let $f(n)$ be the above expression. We know $f(k+1) = (2^k+1)-(2^{k+1}+1) = -2^k$. We claim $f(n+1)-f(n)=1$ for all $n>k$. Indeed, \begin{align*} f(n+1)&= (2^k+1)+\cdots+(2^{n-1}+1)+(2^n+1) - (2^{n+1}-1),\\ f(n)&=(2^k+1)+\cdots+(2^{n-1}+1) - (2^n+1) \\ \implies f(n+1)-f(n) &= (2^n+1)-(2^{n-1}-1) + (2^n+1) = 1. \end{align*}Therefore, $f(k+1 + 2^k+1)=1$, so setting $n=2^k+k+2$ works. $\blacksquare$ Now it is easy to see by induction on $n\in \mathbb{N}$ that we can reach all $n$.

Note that this following claim essentially implies the problem. Claim: For any $n$, we can go from $n$ to $n+1$ in a finite number of moves. Proof: Suppose that the move made from $n$ is the $k$th total move Kelvin has made. Now for each $k \leq i \leq 2^k + k - 1$, send Kelvin $2^i +1$ to the left, and finally send Kelvin $2^{2^k+k}+1$ to the right. I claim that this shifts Kelvin's position right by exactly $1$. Indeed, one can check that $$\sum _{i = k} ^{2^k+k-1} 2^i + 1 = \sum _{i=k} ^ {2^k+k-1} 2^i + 2^k = (2^{2^k+k} - 1) - (2^k-1) + 2^k = 2^{2^k+k} $$which is exactly $1$ less than $2^{2^k+k} + 1$, as desired.

utkarshgupta wrote: An immortal flea jumps on whole points of the number line, beginning with $0$. The length of the first jump is $3$, the second $5$, the third $9$, and so on. The length of $k^{\text{th}}$ jump is equal to $2^k + 1$. The flea decides whether to jump left or right on its own. Is it possible that sooner or later the flee will have been on every natural point, perhaps having visited some of the points more than once? Plain Old Russian Beauty!

Solution with fukano_2. We prove the statement with induction, with the base case (jumping on $n=0$) is trivial. Claim. if we achieve $n$, we can get to $n+1$. Proof. We show that there exists a choice of $b$ such that \[(2^a+1)+(2^{a+1}+1)+\cdots +(2^{b-1}+1)-(2^b+1)=1,\]which obviously proves the claim. Simply select $b=2^a+a+2$; the sum evaluates to \begin{align*} S&=(2^a+1)+(2^{a+1}+1)+\cdots +(2^{b-1}+1)-(2^b+1)\\&= 2^a(2^0+2^1+\cdots + 2^{b-a-1})+(b-a)-(2^b+1)\\&= 2^a(2^{b-a}-1)+(b-a)-(2^b+1)=2^b-2^a+b-a-2^b-1\\&=b-2^a-a-1=2^a+a+2-2^a-a-1=1, \end{align*}as needed.

utkarshgupta wrote: An immortal flea jumps on whole points of the number line, beginning with $0$. The length of the first jump is $3$, the second $5$, the third $9$, and so on. The length of $k^{\text{th}}$ jump is equal to $2^k + 1$. The flea decides whether to jump left or right on its own. Is it possible that sooner or later the flee will have been on every natural point, perhaps having visited some of the points more than once? You spelled "flea" as "flee" on the title and the OP

The answer is yes. Assume it is possible to reach $n$ at the $k^{\text{th}}$ jump. Now assume the flea jumps to the right till the next $r$ jumps. Position after $r$ jumps would be $$n + 2^{k+1} + 1 + \cdots + 2^{k+r} + 1 = n + 2^{k+r+1} - 2^{k+1} + r$$Again assume at the $k+r+1^{\text{th}}$ jump the flea jumps to it's left. So then position at the $k+r+1^{\text{th}}$ jump will be $$=n + 2^{k+r+1} - 2^{k+1} + r - 2^{k+r+1} - 1 = n - 2^{k+1} + r - 1$$Setting $r = 2^{k+1} + 2$ we get that the position at the $k+r+1^{\text{th}}$ jump would be $n+1$. This shows it is possible to reach from the number $n$ to the number $n+1$. To show that it is possible to reach $1$, jump left $2$ times and at the $3^{\text{rd}}$ jump, jump to the right. Edit: Did I misread the problem? (If so, I might edit it later).

Claim. There exists $n$ such that the following is true for any $x$, $$(2^{n+1}+1)-(2^{n}+1)-\ldots-(2^{x}+1)=1.$$Proof. Indeed, this is equivalent to $2^{x}+x=n+1.$ $\square$ Now, define $\{a_n\}$ as $a_{i+1}=2^{a_i}+a_i+1$ and $a_1=1$. Now in $k$th jump if $k=a_i-1$ the flea moves right and otherwise it moves left. We achieve every natural, done.

We claim that it is possible to reach every positive integer. Suppose we want to reach a positive integer $n$. We go $n+3$ steps to the right and $1$ step to the left. The position of the flea is, \begin{align*} & \left(\sum_{i=1}^{n+3}2^i + 1\right) - 2^{n+4} - 1 \\ =&\ 2^{n+4} - 2 + n+3 - 2^{n+4} - 1\\ =&\ n \end{align*}edit: oops misread the problem

Any OTISer? We will claim that it is possible that Kelvin reaches all the positive integer coordinates at least once. First, lets define a sequence where $a_1=1$ and $\forall n\ge 2, a_n=a_{n-1}+2^{a_{n-1}}+1$. The first few terms of this sequence are $1, 4, 21$. Then lets now make some sets of numbers. \begin{align*} &\{ -(2^1+1), -(2^2+1), 2^3+1 \} \\ &\{ -(2^4+1), -(2^5+1), \dots, -(2^{19}+1), 2^{20}+1 \} \\ \vdots \\ &\{ -(2^{a_k}+1), -(2^{a_k+1}+1), \dots, -(2^{a_{k+1}-2}+1), 2^{a_{k+1}-1}+1 \} \end{align*} Now we can see that the sum of all the numbers in each of these sets is equal to 1. Thus if we add together all of these sets we will reach every natural number. $\blacksquare$

Define $$S_{k,\ell}=-2^{\ell+k+1}-1+\sum_{i=\ell}^{\ell+k}(2^i+1)=-2^{\ell+k+1}-1+(k+1)+2^{\ell}(2^{k+1}-1)=k-2^{\ell}.$$If we choose $k=2^{\ell}+1,$ this sum becomes $1.$ Hence, choosing $(k_1,\ell_1)=(1,2^1+1)$ and $(k_i,\ell_i)=(\ell_{i-1}+k_{i-1}+2,2^{\ell_{i-1}+k_{i-1}+2}-1)$ for $i\ge 2,$ we obtain disjoint sums that all have sum one. We claim by induction that the flea can visit all natural numbers. For the base case, the flea can get to one by $S_{k_1,\ell_1}.$ For the inductive step, from $m,$ the flea can use $S_{k_{m+1},\ell_{m+1}}$ to get to $m+1.$ $\square$

The answer is yes. We define $a_k$ the number of steps needed to go from $0$ to $k$. Note that $1=-(2^1+1)-(2^2+1)+(2^3+1)$ $2=1-(2^4+1)-(2^5+1)-\cdots-(2^{4+2^4-1}+1)+(2^{4+2^4}+1)$ $3=2-(2^{4+2^4+1}+1)-(2^{4+2^4+2}+1)-\cdots-(2^{4+2^4+2^{4+2^4}-1}+1)+(2^{4+2^4+2^{4+2^4}}+1)$ $k=(k-1)-(2^{a_{k-1}+1}+1)-(2^{a_{k-1}+2}+1)-\cdots-(2^{a_{k-1}+2^{a_{k-1}-1}}+1)+(2^{a_{k-1}+2^{a_{k-1}}}+1)$ $k+1=k-(2^{a_{k}+1}+1)-(2^{a_{k}+2}+1)-\cdots-(2^{a_{k}+2^{a_{k}-1}}+1)+(2^{a_{k}+2^{a_{k}}}+1)$ So by induction we get that $n=(n-1)-(2^{a_{n-1}+1}+1)-(2^{a_{n-1}+2}+1)-\cdots-(2^{a_{n-1}+2^{a_{n-1}-1}}+1)+(2^{a_{n-1}+2^{a_{n-1}}}+1)$ Thus the flea can visit all points with positive integer coordinates.

It is possible. It suffices to show that from any point $n$ on the number line, Kelvin can get to $n+1$. Suppose that Kelvin has already jumped $k$ times. Then, we may jump the next $2^{k+1}+1$ jumps in the negative direction, and then the next jump in the positive direction: this yields a net difference of $$-\left(2^{k+1} + 2^{k+2} + \cdots + 2^{k+2^{k+1}} + 2^{k+1}\right) + 2^{k+1+2^{k+1}} + 1 = 1,$$which means that Kelvin can reach $n+1$, as required.

We claim that the answer is positive. It's suffice to prove, that from point $n$ flea can jump to $n+1;$ if flea reached point $n$ on $k-$th move, let it makes $2^{k+1}$ jumps to left and one jump to right - it works, since the new coordinate is $$n+2^{k+2^{k+1}+1}+1-\sum_{i=1}^{2^{k+1}} (2^{k+i}+1)=n+1.$$

Lemma 1: For any positive integer $n$, $$(2^{2^n+n}+1)-((2^n+1)+(2^{n+1}+1)\cdots +(2^{2^n+n-1}+1))=1.$$This is because $$(2^{2^n+n}+1)-((2^n+1)+(2^{n+1}+1)\cdots +(2^{2^n+n-1}+1))$$$$=2^{2^n+n}-2^{2^n+n-1}\cdots -2^n-(2^n-1)=1.$$ Now, define the sequence $a_n$ recursively as $$a_1=1,a_n=2^{a_{n-1}}+a_{n-1}+1,$$so for example the first 4 terms are $1,4,21,2097174.$ Now, by Lemma 1, observe that $$(2^{a_2-1}+1)-\sum_{i=a_1}^{a_2-2} 2^i+1=1$$$$(2^{a_3-1}+1)-\sum_{i=a_2}^{a_3-2} 2^i+1=1,$$and so on so in general $$(2^{a_{n+1}-1}+1)-\sum_{i=a_n}^{a_{n+1}-2} 2^i+1=1,$$so we can employ an algorithm where we move forwards if the move number is of the form $a_n-1$ for some $n$, and move backwards otherwise. This allows us to reach $n-1$ on move $a_n-1$ due to the prefix sums, so we are done.

We claim that it is possible. The flea can simply jump right for the first $k$ moves, and then jump left on the $k+1$th move. Representing the jumps as numerical values, we can write the expression as \begin{align*} \sum _{n = 1} ^{k} (2^n + 1) - (2^{k+1}+1) = k + 2^{k+1} - 1 - 2^{k+1} = k - 1 \end{align*} Since $1 \le k \le + \infty$, we are done. $\blacksquare{}$

Notice how $2^{n+1}-1=2^n+2^{n-1}+\dots +2+1$, so we can write \[2^{n+1}+1=(2^n+1)+(2^{n-1}+1)+\dots (2+1)-(n-3).\]Rearranging, we get \[(2^n+1)+(2^{n-1}+1)+\dots +(2+1)-(2^{n+1}+1)=n-3\]so take $n=k+1$, where $k$ is the value we want to get. Therefore, it is possible.

$$2^k+1+2^{k+1}+1+\cdots+2^{k+2^k-1}+1-(2^{k+2^k}+1)=2^k(2^{2^k}-1)+2^k-(2^{k+2^k}+1)=-1$$ So randomly move to a very very big number,then come back with this algorithm,then repeat $\blacksquare$

WLOG, assume the immortal flea is tricking us and is actually a frog. Now, call the frog Kelvin.

At any point, if the flea makes right jumps $2^a + 1, 2^{a + 1} + 1, \dots, 2^{a + n - 1} + 1$ then does a left jump of $2^{a + n} + 1$, its net change in distance is $$\sum_{i = a}^{a + n - 1} (2^i + 1) - (2^{a + n} + 1) = 2^a(2^n - 1) + n - (2^{a + n} + 1) = n + 1 - 2^a.$$From here, simply choose $n = 2^a$ which in total moves the flea to the next integer. Then repeat this process starting at $0$ and we are guaranteed to have visited every nonnegative integer at least once.