Consider two copies of graphs with $m$ vertices amd $2m$ edges, e.g. of $K_5$, the complete graph with $m=5$ vertices. With two copies, you have $n=2m$ vertices and $2n$ edges, but the graph is not connected. Therefore the claim is false.
I'm sorry, but your proof is incomplete; you fell into the so-called "induction trap".
For the induction step, you assume that any connected graph with $k$ vertices has at least $k-1$ edges; and you want to prove that any connected graph $G$ with $k+1$ vertices has at least $k$ edges. In trying to prove this, you assume that $G$ was obtained by adding a new vertex (which you confusingly call $k'$) to a connected graph with $k$ vertices. But you have not justified this assumption.
To justify your argument, you would have to show that every connected graph with $k+1$ vertices can be obtained by adding a vertex (and some edges) to some connected graph with $k$ vertices. In other words, you have to show that, given any connected graph with $k+1$ vertices, you can find a vertex whose deletion results in a connected graph. This is true, but requires a proof. (Well, it's true for finite graphs, which is what we're talking about. In a connected infinite graph, it's possible that deleting any vertex disconnects it.)
For an alternative approach, you can delete an arbitrary vertex $v$ from a $k$-vertex graph $G$, without worrying about whether $G-v$ is connected or not; you then apply the induction hypothesis to each connected component of $G-v$, however many there may be. In this approach, you have to use the style of induction where you prove the statement for $k$ assuming that it holds for all numbers smaller than $k$.
Best Answer
Following up on David's suggestion in the comments: you should show that the given conditions imply that your graph must be a tree (there are many ways to do this, but a visually appealing approach would be to induct on the number of vertices). Once you have done this, you can argue by contradiction: if you have two distinct paths between vertices $u$ and $v$, then putting them together there will have to be a cycle somewhere in the graph.