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.
Best Answer
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.