Prove there exist infinite subsequences of $x_{n+1} = x_n + 2^n$ all members of which are divisible by $3$

Question

First, let $p \in \mathbb{N}$, and consider the following sequence $x_1,x_2,\ldots, x_n$ recursively defined:

$$ \begin{cases} x_1 = p \\ x_{n+1} = x_n + 2^n \end{cases} $$ I want to show that, for any $p \in \mathbb{N}$ there are an infinite number of positive integers $n$ such that $x_n$ as specified above is divisible by $3$. (If that is not possible, I would like to show that there exists a $p \in \mathbb{N}$ such that there are an infinite number of positive integers $n$ such that $x_n$ as specified above is divisible by $3$.)

---

My work so far: I've started with a try to find the closed form to see whether i can infer something from there. So I expanded the terms and observed a pattern:

$$ \begin{align} x_1 &= p \\ x_2 &= x_1 + 2 = p + 2 \\ x_3 &= p + 2 + 2^2 \\ &\cdots \\ x_n &= p + 2 + 2^2 + \cdots + 2^{n-1} \end{align} \\ x_n = p + \sum_{k=1}^{n-1}2^k = p+2^n -2 $$

It's simple to show that it holds for $n+1$ by induction, so the formula seems correct at the point. To confirm i get the same result by other method i've done the following: $x_n = x_n^{(h)} + x_n^{(p)}$. Now for homogenous part: $$ \begin{align} x_{n+1} - x_n &= 0 \\ \lambda - 1 &= 0\\ \lambda &= 1 \implies \\ \implies x_n^{(h)} &= A\cdot \lambda^n = A \end{align} $$

For particular: suppose solution is in the form $B\cdot 2^n$:

$$ B\cdot 2^{n+1} - B\cdot 2^n = 2^n \\ 2B - B = 1 \\ B = 1 $$

So:

$$ \begin{align} x_n &= A + 2^n \\ x_1 &= p = A + 2 \iff A = p -2 \implies \\ \implies x_n &= p + 2^n - 2 \end{align} $$

That is where I got stuck.

After I have a closed form of the recurrence how do i prove there exist subsequences all members of which are divisible by $3$? I can imagine the above is not even necessary and one may find a smarter way without involving the general term formula.

Answer 1

It looks false to me. Suppose $x_1=5$, then you get $5,7,11,19 \dots$ none of which are divisible by $3$.

Note that $2\equiv -1 \bmod 3$ so the powers of $2$ alternate between $+1\bmod 3$ and $-1\bmod 3$, so the values of $x_n$ occupy just two of the three residue classes modulo $3$. You can always arrange to miss the multiples of $3$ by starting in the right place.

---

Note I chose $p=5$, an odd prime, in case this was intended by the use of the letter $p$ - $2$ or $8$ or any number of the form $3n+2$ will do.

Answer 2

For $x_{n+1} = x_{n} + 2^{n}$, where $x_{1} = p$, the, as determined, the solution is $x_{n} = p + 2^{n} - 2$. Now, consider $\phi_{n} = 2^{n} -1$ which has the property $3|\phi_{2n} \hspace{3mm} n \geq 0$. With this in mind then for even $n$ it is seen that $$x_{2n} = (p-1) + (2^{2n} - 1)$$ and $ 3| x_{2n} = \alpha + q_{n}$, where $q_{m} = 3|\phi_{2m} \in \{0, 1,5, 21, \cdots \}_{m \geq 0}$ and $\alpha = (p-1)/3$. If $p$ takes the form $3 \, r + 1$ then $$3|x_{2n} = r + q_{n}.$$

Note: if $p$ is a prime then the values that take the form $p = 3 \, r + 1$ are $p \in \{7, 13, 19, 31, 37, 43, \cdots \}$ for which $r$ takes the values $r \in \{2, 4, 6, 10, 12, 14, \cdots \}$.

Answer 3

$$(2^n-1)\bmod3=0,1,0,1,0,1,0,1,\cdots$$

and the claim is wrong (unless we are free to choose $p$).

Answer 4

Note $x_n = p + \sum\limits_{i=1}^{n-1} 2^i$

$2^{i} \equiv (-1)^i (\mod 3)$ and $\sum\limits_{i=1}^{n-1} 2^i \equiv 0,-1(\mod 3)$ if $n$ is odd or even respectively.

So if $p \equiv 0(\mod 3)$ then $x_n \equiv 0 \pmod 3$ if $n$ is odd.

If $p \equiv 1\pmod 3$ then $x_n \equiv 0\pmod 3$ if $n$ is even.

If $p \equiv -1\pmod 3$ then $x_n\equiv -1\pmod 3$ if $n$ is odd and $\equiv 1\pmod 3$ if $n$ is even and never divisible by $3$.

So the claim is false.