<s>[INST] Divisibility of $n\cdot2^n+1$ by 3. I want to examine and hopefully deduce a formula that generates all $n\geq0$ for which $n\cdot2^n+1$ is divisible by $3$. Let's assume that it is true for all $n$ and that there exist a natural number $k\geq0$ such that $$n\cdot2^n+1=3k,$$
Now I want to proceed with induction, but clearly this will not work because for $n=3$ we have $3\cdot2^3+1=3\cdot8+1=24+1=25$ which is clearly not divisible by $3$. 
Any ideas how to evaluate a formula that generates all the $n$'s for which $n2^n+1$ is divisible by $3$?
 [/INST] This is an approach which does not use (directly) modular arithmetic.
Set $a_n = n 2^n + 1$.
Let's define $S:=\{ n\in \mathbb{Z} \mid n \geq 0 \text{ and $3$ divides $a_n$} \}$. Observe that for integers $n,k \geq 0$:
$$ a_{n+k} - a_n = (n+k) 2^{n+k} - n 2^n = 2^n((n+k)2^k - n) = 2^n((2^k-1)n +k2^k) $$
For $k=6$ we get:
$$ a_{n+6} - a_n =2^n( 63n +6\cdot 64) =3 \cdot 2^n( 21n +128)  \quad \Rightarrow \quad 3 \text{ divides } (a_{n+6} - a_n)$$
If two integers $a,b$ are multiple of $3$ then also $a+b$ and $a-b$ are multiple of $3$. Since clearly:
$$a_{n+6}=(a_{n+6} - a_n)+a_n \quad\text{ and }\quad a_n=a_{n+6} -(a_{n+6} - a_n)$$
then $3$ divides $a_n$ if and only if $3$ divides $a_{n+6}$. In other words, $n\in S$ if and only if $n+6 \in S$.
This can be used to prove by induction that the general element of $S$ can be written as $n=x+6k$, where $k$ is any integer satisfying $k\geq 0$ and $x$ is an element of $S$ satisfying $0\leq x <6$.
Now let's see which $x$ satisfying $0\leq x <6$ are in $ S$ :
$$
\begin{align}
a_{0}&= 1 & &\Rightarrow 0 \notin S\\
a_{1}&= 2 + 1 = 3 & &\Rightarrow 1 \in S\\
a_{2}&= 2\cdot 2^2 + 1= 9 & &\Rightarrow 2\in S\\
a_{3}&= 3\cdot 2^3 + 1= 25 & &\Rightarrow 3\notin S\\
a_{4}&= 4\cdot 2^4 + 1= 65 & &\Rightarrow 4\notin S\\
a_{5}&= 5\cdot 2^5 + 1= 161 & &\Rightarrow 5\notin S
\end{align}$$
Therefore:
$$ S=\{1+6k,2+6k\; \text{ s.t. }\; k \geq 0\} $$
</s>