In the beginning, we must show that mapping $p_a: G \to G: p_a(x) = a^{-1}xa$ exists. Then we will show, that it is injective and surjective. If so, then it is isomorphism and automorphism.
Because $(G,\cdot)$ is a group, for $a \in G $ and $x \in G$: $a^{-1}xa \in G$. Because of that, we can safely define $p_a: G \to G: p_a(x) = a^{-1}xa$, knowing that we begin and end in $(G,\cdot)$.
Let's assume that $p_a$ isn't injective. Then $\exists x_1,x_2 \in G, x_1 \ne x_2, $ such as $p_a(x_1) = p_a(x_2)$. Then $a^{-1}x_1a = a^{-1}x_2a$. $(G,\cdot)$ is a group, so we can "multiply" this expression by $a$ from the left side and by $a^{-1}$ from the right side: $aa^{-1}x_1aa^{-1} = aa^{-1}x_2aa^{-1} \Rightarrow x_1=x_2$, but $x_1 \ne x_2$. Therefore $p_a$ must be injective.
Let's assume that $p_a$ isn't surjective. Then $\exists y \in G: \forall x \in G:f(x) \ne y$. Then $a^{-1}xa \ne y$. We can transform it into $\exists y \in G: \forall x \in G: a^{-1}ya \ne x $. But that cannot be, because that means that result of $a^{-1}ya$ isn't in $(G,\cdot)$. Therefore $p_a$ must be surjective.
Now, for the second part, we should prove two things: that $Inn(G)$ is a subgroup of $Aut(G)$, and that it is a normal subgroup.
We must show that neutral element of $Aut(G)$ is in $Inn(G)$. We don't know how he looks like, but it isn't hard to guess that $id$ is a neutral element of $Aut(G)$. $id(x) = x$, so we must find $p_a$ with same properties. It isn't hard, too: $p_1(x) = 1 \cdot x \cdot 1 = x$. So $id = p_1, p_1 \in Inn(G)$.
Then, we must show that $\forall p_a,p_b \in Inn(G)$, $p_b \circ p_a \in Inn(G)$. $(p_b \circ p_a)(x) = p_b(p_a(x)) = p_b(a^{-1}xa) = b^{-1}a^{-1}xab = (ab)^{-1}x(ab) = p_{ab}(x) \in Inn(g)$.
Third part is existence of inverse element to $p_a$ in $Inn(G)$. This element would be $p_{a^{-1}}$: $(p_{a^{-1}} \circ p_a)(x) = (aa^{-1})^{-1}x(aa^{-1}) = 1 \cdot x \cdot 1 = x$.
Finally, we must show that $Inn(G)$ is a normal subgroup: for $f,f^{-1} \in Aut(G), p_a \in Inn(G):$ $(f^{-1} \circ p_a \circ f)(x) = f^{-1}(p_a(f(x))) = f^{-1}(a^{-1} \cdot f(x) \cdot a) = f^{-1}(a^{-1}) \cdot f(f^{-1}(x)) \cdot f^{-1}(a) = f^{-1}(a^{-1})\cdot x\cdot (f^{-1}(a^{-1}))^{-1}$. $f(x)$ is in $G$, so are $f^{-1}(a^{-1})$ and $(f^{-1}(a^{-1}))^{-1}$, and $f^{-1}(a^{-1})\cdot x\cdot (f^{-1}(a^{-1}))^{-1}$ defines another $p_b \in Inn(G)$. The proof is complete.
For any given $a \in G$, conjugacy by $a$, namely the map $\varphi_a \colon G \to G$ defined by $\varphi_a(g):=aga^{-1}$, is an automorphism of $G$. In fact, $\varphi_a(g)=\varphi_a(g') \Rightarrow aga^{-1}=ag'a^{-1} \Rightarrow g=g'$ (injectivity); then, for evey $g\in G, \varphi_a(a^{-1}ga)=g$ (surjectivity); finally, $\varphi_a(gg')=agg'a^{-1}=aga^{-1}ag'a^{-1}=(aga^{-1})(ag'a^{-1})=\varphi_a(g)\varphi_a(g')$ (homomorphism). Therefore, $\Phi:=\{\varphi_a, a \in G\} \subseteq \operatorname{Aut}(G)$.
Now, $(\varphi_a\varphi_b)(g)=\varphi_a(\varphi_b(g))=a(bgb^{-1})a^{-1}=(ab)g(ab)^{-1}=\varphi_{ab}(g)$, whence $\varphi_a\varphi_b=\varphi_{ab} \in \Phi$ (closure); then, $(\varphi_a\varphi_{a^{-1}})(g)=\varphi_a(\varphi_{a^{-1}}(g))=a(a^{-1}ga)a^{-1}=g$, whence $\varphi_a^{-1}=\varphi_{a^{-1}}\in \Phi$ (closure by inverses). Therefore, $\Phi \le \operatorname{Aut}(G)$.
Let's now prove that $\Phi \unlhd \operatorname{Aut}(G)$. Well, $\forall a,b \in G, \forall \sigma \in \operatorname{Aut}(G)$, we get: $(\sigma^{-1}\varphi_a\sigma)(b)=\sigma^{-1}(\varphi_a(\sigma(b)))=\sigma^{-1}(a\sigma(b)a^{-1})=$ $\sigma^{-1}(a)b\sigma^{-1}(a^{-1})$; call $\tau:=\sigma^{-1} \in \operatorname{Aut}(G)$, then $(\sigma^{-1}\varphi_a\sigma)(b)=\tau(a)b\tau(a^{-1})=\tau(a)b\tau(a)^{-1}=\varphi_{\tau(a)}(b)=\varphi_{\sigma^{-1}(a)}(b)$, so that $\sigma^{-1}\varphi_a\sigma=\varphi_{\sigma^{-1}(a)} \in \Phi$. $\Box$
$\Phi$ is precisely $\operatorname{Inn}(G)$.
Best Answer
You can do that via this fact that $Inn(G)$ is non empty (You have shown this) and the fact that for all $g,h\in G$ $$f_gf_h=f_{gh}$$ so $$f_gf_g^{-1}=f_e$$ where $e$ is the identity of the group (You can see that $f_e$ is the identity of $Aut(G)$). so $$(f_g)^{-1}=f_{g^{-1}}$$ and from this we have $$(f_g)^{-1}f_h=f_{g^{-1}}f_h=f_{hg^{-1}}\in Inn(G)$$ Here we satisfy the condition in which any subset of a group should have to be a subgroup.