When does $n$ divide $2^n+1$? 
For which $n$ does $n\mid2^n+1$ ?

My hypothesis is that the only solution is $n=3^k$, for some positive integer $k$.  
 A: Unfortunately, your claim is false. 
You can find a list where $2^n+1 \equiv 0 \pmod {n}$ here.
The smallest counterexample is $n =171$ as can be seen on the sequence. 
There are some more comments here. 
Interestingly, the sequence is closed under multiplication, so if $x,y$ are part of the sequence then $xy$ is as well, as is proven in the paper. 
Since $3$ is part of the sequence, it follows that every number of the form $3^n$ is going to be on the sequence. So, it is true that $$2^{3^{n}} +1\equiv  0 \pmod {3^n}$$
Furthermore, we can prove that every member of the sequence is a multiple of $3$.  
A: For interest and accessibility, I'll reproduce a result from the paper cited by SCB above:

Proposition: If $p \mid n$ and $n \mid 2^n{+}1$ then $pn \mid 2^{pn} {+} 1$. 
Proof: Clearly  $p > 2$. Set $M = 2^n$, giving $2^{pn} + 1 = (M + 1)(M^{p−1} − M^{p−2} + ... − M + 1)$.
Now $n \mid M{+}1$ and thus $M \equiv -1 \bmod p$ so
  $\begin{align}M^{p−1} − M^{p−2} + ... − M + 1 &\equiv (−1)^{p−1} − (−1)^{p−2} + ... − (−1) + 1 = p \\
& \equiv 0 \bmod p 
\end{align}$
  so that $pn \mid 2^{pn} {+} 1$

Since $3 \mid 2^3{+}1$, this also immediately gives $3^{k} \mid 2^{3^k}{+}1$. 
Also (for example) given that $171 \mid 2^{171}{+}1$ and $3^2\cdot 19 = 171$,  we will have $c\mid 2^c{+}1$ for any $c=3^a\cdot 19^b$ with $a\ge2$

Thomas Andrews points out that we only need to have $p \mid 2^n{+}1$ (rather than $p\mid n$) for the above result. This allows us directly into some non-powers-of-$3_\mathstrut$ solutions: for example, because $(n,p)=(9,19)$ with $9 \mid 2^9{+}1$ and $19\mid 2^9{+}1$, the result follows that $9\cdot 19 = 171 \mid 2^{171}{+}1$
A: More generally:

If $n\mid 2^{n}+1$ and $d\mid 2^n+1$ then $nd\mid 2^{nd}+1$.

This is because $n$ and $d$ are odd, so if $2^{n}\equiv -1\pmod d$ then $(-2)^n\equiv 1\pmod d$ and $$\begin{align}\frac{2^{nd}+1}{2^n+1}&=\frac{1-((-2)^n)^d}{1-(-2)^n} \\
&= 1+(-2)^n+(-2)^{2n}-\cdots +(-2)^{n(d-1)}\\
&\equiv 1+1+1+\cdots 1 \\&= d\equiv 0\pmod{d}.\end{align}$$
So $(2^n+1)d\mid 2^{nd}+1$ and hence $nd\mid 2^{nd}+1$.
So we can say a solution $n$ is absolutely primitive if, for each prime $p\mid n$,  $2^{n/p}+1$ is not divisible by $\mathrm{lcm}(n/p,p).$
For example, $171=3^2\cdot 19$ is not absolutely primitive because $\mathrm{lcm}(171/19,19)=171\mid 2^{171/19}+1$. And $3$ is not primitive since $\mathrm{lcm}(3/3,3)=3\mid 2^{3/3}+1$.
Indeed, I wonder if there are any absolutely primitive $n$ other than $1$.
If prime $p\mid n$ and $p\mid 2^n+1$ then $2^{n}=( 2^{n/p})^p\equiv 2^{n/p}\pmod p$ and hence if $n$ is absolutely primitive, then $\frac{n}{p}$ can't be a divisor of $2^{n/p}+1$ for any prime divisor $p$ of $n$.
Now given two distinct prime factors $p,q$ of $n$, if $q^k\mid 2^n+1$ and $q^k\not \mid 2^{n/p}+1$ then we must have $q\mid \sum_{i=0}^{p-1} (-2)^{ni/p}$. But if $q\mid 2^{n/p}+1$, we'd have $(-2)^{n/p}\equiv 1\pmod{q}$ and thus $q\mid p$, which is not possible.
This means that, if $n$ is absolutely primitive, then for each prime $p\mid n$ there must be another prime $q\mid n$ such that $q\not\mid 2^{n/p}+1$ and $q\mid 2^{n}+1$.
But if $2^{n/p}+1$ is not divisible by $q$ and $2^{n}+1$ is divisible by $p$, then $-1$ must be a non-trivial $p$th power, modulo $q$, and thus $q-1$ must be divisible by $p$. 
So if $p$ is the largest prime factor of $n$, we get that no such $q$ can exist.
Therefore, for any $n$ with $n\mid 2^n+1$ either $n=1$ or the largest prime $p\mid n$ satisfies $\frac{n}{p}\mid 2^{n/p}+1$ and $p\mid 2^{n/p}+1$.
A: It is not necessary that $n = 3^k$, but it is sufficient.
Using the Lifting the Exponent Lemma, if $p$ is a prime and $a$ and $b$ are natural numbers not divisible by $p$, assuming $p|a+b$, then $$v_p(a^n+b^n)=v_p(a+b) + v_p(n).$$
Now putting $p=3$, $a=1$ and $b=2$, we get $$3^{n+1} | 2^{3^n}+1.$$
