Show that $a^{m} a^{n} = a^{m+n}$ Prove that if $G$ is a group and $a\in G$, then we have $\forall m,n\in\mathbb{Z} $ that 
$$a^{m} a^{n} = a^{m+n}.$$
I've proved the case when $m,n>0$ but I'm stuck on how to prove the case when one or both are negative without assuming that $(a^{-1})^n = a^{-n} $. 

You have to consider a few cases to prove this theorem. In that way, I find it a bit annoying. Perhaps there is a better way, but I do not know of one. 
Edit: There actually is a straightforward way of shortening this; see A.P.'s comment. 
You have considered one such case ($m,n > 0$). Here we will prove (most of) the others. We will call case (i) the one you proved and begin with case (ii). The identity will be denoted $e$.
As for your question regarding $(a^{-1})^n=a^{-n}$, we have that $(a^{-1})^n=(a^n)^{-1}$ and that is, by definition of the notation, equal to $a^{-n}$.
Now, let us complete the proof by considering the other cases.
(ii) Suppose $n=0$, then $a^{m+n}=a^{m+0}=a^m$ and $a^m a^n=a^m a^0 = a^m e = a^m$, hence $a^{m+n}=a^m a^n$.
(iii) Suppose $n<0, m=-n$, then $a^{m+n}=a^0=e$, hence $a^m=a^ma^{-m}=e$ (this too is worth proving), so $a^m a^n = a^{m+n}$.
(iv) Suppose $n<0, m<-n$, then 
$$\begin{aligned} 
a^m a^n & = a^m (a^{-1})^{-n} \\ 
& = a^m (a^{-1})^{m-(m+n)} \\ 
& = a^m \left((a^{-1})^m (a^{-1})^{-(m+n)} \right) \\ 
& = a^m \left( a^{-m}(a^{-1})^{-(m+n)}\right) \\ 
& = (a^m a^{-m}) (a^{-1})^{-(m+n)}  \\ 
& = e (a^{-1})^{-(m+n)} \\ 
& = a^{m+n} 
\end{aligned}$$
(v) Suppose $n<0, m>-n$, then 
$$\begin{aligned}
a^m a^n & = a^{(m+n)+(-n)}a^n \\
& = (a^{m+n}a^{-n})a^n \\
&= a^{m+n}(a^{-n}a^n) \\
&= a^{m+n} e \\
&= a^{m+n}
\end{aligned}$$
Thus far we have proven that for a fixed $m>0$ we have the identity for all $n$, whether $n<0$, $n=0$, or $n>0$. To be complete we would have to show the same for fixed $m<0$ and $m=0$. For $m=0$ we have an easy verification; for $m<0$ one can go through a similar argument as above. These cases will be left to the reader, mainly because I am too lazy to write it all out.
Hence, we have proved that if $a \in G$, then for all $m,n \in \mathbb{Z}$ 
$$a^m a^n = a^{m+n}$$
$\blacksquare$
