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$?
 A: It should also be clear that if $n$ is divisible by $3$, then $n\cdot 2^n$ is divisible by $3$ so $n\cdot 2^n + 1$ is not divisible by $3$.
Therefore, the only candidates are $n=3k+1$ and $n=3k+2$.
Now, look at the remainders of $2^n$ when divided by $3$:
$$2^1\equiv 2\mod 3\\
2^2\equiv 1\mod 3\\
2^3\equiv 2\mod 3\\
2^4\equiv 1\mod 3\\
2^5\equiv 2\mod 3\\\vdots$$
and so on. You can clearly see that $2^k\equiv 2\mod 3$ for odd $k$ and $2^k\equiv 1\mod 3$ for even $k$.

So, let's look at the whole expression depending on how $n$ is divisible by $6$:


*

*If $n\equiv 0\mod 6$, then $n$ is divisible by $3$, so $n\cdot2^n+1$ is not divisible by $3$.

*If $n\equiv 1\mod 6$, then $n$ is odd, so $2^n\equiv 2\mod 3$. Since $n\equiv 1\mod 3$, this means $$n\cdot 2^n\equiv 1\cdot 2\equiv 2\mod 3$$ meaning that $n\cdot 2^n+1\equiv 2+1=3\equiv 0\mod 3$ so $n\cdot2^n+1$ is divisible by $3$

*If $n\equiv 2\mod 6$, then $n$ is odd and $n\equiv 2\mod 3$. Because $n$ is odd, $2^n\equiv 1\mod 3$, and therefore $n\cdot 2^n\equiv 2\cdot 1\equiv 2\mod 3$ meaning $n\cdot 2^n+1\equiv 2+1\equiv 0\mod 3$, so again, $n\cdot 2^n +1$ is divisible by $3$.


I trust you can finish the rest of the cases yourself...
A: The sequence $a_n=n\cdot 2^n$ satisfies the recursion
$$
a_0=0,\quad a_1=2,\quad a_{n+2}=4a_{n+1}-4a_n
$$
Indeed, if we assume the thesis to hold for all $k<n$, with $n>2$, we have
$$
a_{n}=4a_{n-1}-4a_{n-2}=4(n-1)\cdot2^{n-1}-4(n-2)\cdot2^{n-2}
=4\cdot2^{n-2}(2n-2-n+2)=n\cdot2^n
$$
If $b_n$ denotes the remainder class of $a_n$ modulo $3$, we have
$$
b_{n+2}=4b_{n+1}-4b_n=b_{n+1}-b_n
$$
and we want to see for what $n$ we have $b_n=2$ (I denote the remainder classes modulo $3$ just by $0$, $1$ and $2$).
It is clear that, whenever two consecutive terms repeat, the sequence will restart with the same terms all over; let's see:
\begin{align}
b_0&=0 \\
b_1&=2 \\
b_2&=b_1-b_0=2 \\
b_3&=b_2-b_1=0 \\
b_4&=b_3-b_2=1 \\
b_5&=b_4-b_3=1 \\
b_6&=b_5-b_4=0 \\
b_7&=b_6-b_5=2
\end{align}
Then $b_8=b_2$, $b_9=b_3$ and so on.
A: $n\cdot2^n+1\equiv0\pmod3\iff n(-1)^n\equiv-1\iff n\equiv(-1)^{n+1}\pmod3$
If $n$ is even, $=2m$(say)  $$2m\equiv-1\pmod3\iff m\equiv1\pmod3\implies n\equiv2\pmod6$$
If $n$ is odd, $=2m+1$(say)  $$2m+1\equiv1\pmod3\iff m\equiv0\pmod3\implies n\equiv1\pmod6$$
A: For any natural number $ n $ we have that $ n \equiv i $ mod $ 3 $ where $ i \in \{0,1,2\} $. So let us consider each case. 
If $ n \equiv 0 $ mod $ 3 $ then clearly $ n2^{n}+1 \equiv 1 $ mod $ 3 $ so this is not a valid case. 
Suppose now that $ n \equiv 1 $ mod $ 3 $ and write $ n=3k+1 $. Then $$ n2^{n}+1=(3k+1)2^{3k+1}+1 \equiv 2^{3k+1}+1   (mod  3)  \equiv 2 \cdot 8^{k}+1  (mod  3 ) \equiv 2 \cdot (-1)^{k}+1 (mod 3) $$
Therefore $ k $ must be even in this case so $ k=2l $ for some integer $ l $ thus $ n=6l+1 $.
Finally, if $ n \equiv 2 (mod 3) $, write $ n=3k+2 $. Then we have $$ n2^{n}+1=(3k+2)\cdot 2^{3k+2}+1 \equiv 2 \cdot 2^{3k+2}+1 (mod 3)\equiv 8^{k+1}+1 (mod 3) \equiv (-1)^{k+1}+1 (mod 3) $$
Hence in this case, we must again have that $ k $ is even i.e. $ k=2l $ for some integer $ l $ so $ n=6l+2 $.
Therefore we conclude that the only positive integers $ n $ satisfying the condition in the hypothesis are those $ n's $ congruent to $ 1 $ or to $ 2 $ modulo $ 6 $.
A: 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\} $$
