<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] 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...
</s>