Suppose by contradiction that $n$ is not prime. Now consider the greatest divisor $d < n$ of $n$. Then we can write $n$ as $de$. Since $n$ is not prime, we have $d > 1$ and hence also $e < n$. Now $e$ must satisfy $e > 1$ and $e \le d$ (because $d$ is the greatest divisor satisfying $d < n$). Now $d+1$ must be a divisor of $n+1$. Moreover, $d+1$ is a divisor of $(d+1)e = de + e = n + e$. This means that $d+1$ must also be a divisor of the difference $n + e - (n+1) = e - 1$. This, however, is impossible, because $e-1$ is a number between 1 and $d-1$. Therefore, our assumption that $n$ is not prime must be false, and $n$ must actually be a prime number. $\square$