Does Andrica's conjecture imply Legendre's conjecture? I have the following reasoning.
Let $p_n$ denote the $n$th prime. Recall that Andrica's conjecture is the following statement: $$ \sqrt{p_{n+1}}-\sqrt{p_n}<1, $$
for all positive nonzero integer $n$. On the other hand, Legendre's conjecture states that there is a prime number between $m^2$ and $(m+1)^2$ for every positive integer $m$. I then propose the following Theorem.
Theorem 1. Andrica's conjecture implies Legendre's conjecture.
Proof. Let $g_n$ denote the $n$th prime gap. Following Andrica's conjecture, we have $g_{n}<2{\sqrt {p_{n}}}+1$, or equivalently $p_{n+1}<2{\sqrt {p_{n}}}+1+p_{n}$.
Now let $N$ be a positive integer greater than $2$ and $p_{n}$ the greatest prime smaller than or equal to $(N-1)^2$. We then have:
\begin{align*} (N-1)^2 & < p_{n+1}\\ & < 2{\sqrt {p_{n}}}+1+p_{n} \\ & < (\sqrt {p_{n}} + 1)^2. \end{align*}
But since $p_{n}<(N-1)^2<p_{n+1}$, we have: \begin{align*} (N-1)^2 & < (\sqrt {p_{n}} + 1)^2 \\ & < (\sqrt {(N-1)^2} + 1)^2 \\ & < (N-1+1)^2 \\ & < N^2. \end{align*}
We have therefore shown that assuming Andrica's conjecture, $(N-1)^2<p_{n+1}<N^2$, i.e., that there is always a prime between $(N-1)^2$ and $N^2$ for all positive integer $N>2$. $$\tag*{$\square$}$$
I recall reading somewhere that one can not imply Legendre's conjecture from Andrica's, so I must be missing something here. What is it?
Indeed, the truth of Andrica's conjecture implies the truth of Legendre's conjecture, and your proof is correct.
As a matter of style, it is not good that you switch from $m^2$ and $(m+1)^2$ used in the statement of Legendre's conjecture to using $(N-1)^2$ and $N^2$ in the proof, it would be better to use the same notation in both. And I would leave the prime gap $g_n$ out of it and write
\begin{align} (N-1)^2 &< p_{n+1} \\ &= (\sqrt{p_{n+1}})^2 \\ &< (\sqrt{p_n} + 1)^2 \tag{Andrica's conjecture}\\ &\leqslant \bigl((N-1) + 1\bigr)^2 \tag{$p_n \leqslant (N-1)^2$}\\ &= N^2\,. \end{align}
But the latter is a matter of taste.