The sign of the spring constant depends on your definition of the spring force.
It may be [tex]\vec{F}=k\vec{x}[/tex], in which it is always negative, or
[tex]\vec{F}=-k\vec{x}[/tex], in which it is always positive (in these cases for ideal springs). The important part is that the spring force always tends to pull or push the spring back to equilibrium.
You cannot prove this. These force expressions are designed to fit experimental data. It is the same as trying to prove that like charges always repel. It just is that way.
Also, as Mapes pointed out, the opposite case leads to a runaway process when the spring is disturbed from (unstable) equilibrium.