The other direction is the tricky one. Assume that <v,x>=0 for any x in N. First, define a subspace U as follows:
It's clear that (I'll leave you to check that if you're not convinced). So in particular, N has a basis, say . We can also assume, without loss of generality, that this basis is orthonormal.
Now, we use the fact that U+N gives the whole vector space (I'm assuming this is a fact you know). Then, v must be a linear combination of 's and 's. So write:
Take any one of the .
Since this must be zero, we get that and since our choice of was arbitrary, all the b's must be zero. So we're left with:
And so v is indeed a linear combination of the 's