Prove that $Z(S_n) = \{(1)\}$ for every $n \geq 3$. Induction I wonder if this questions can be done by induction.
$S_3 = \{(1),(12),(13),(23),(123),(132)\}$
$Z(S_3)$ contains all the elements in $S_3$ that commutes with all the element in $S_3$
We can easily proof the base case for $n=3$ 
However, I have a hard time proving the induction step.
Assume $Z(S_k) = \{1\}$  then now we need to show it works for $Z(S_{k+1})$
The thing is $S_{k+1}$ contains $(k+1)|S_{k}|$ elements which is $(k+1)k!$
But can I go anywhere from here ?
 A: Here's an induction "proof". I'll explain the scare quotes at the end.

Base Case: verify $S_3$.
Induction: Assume for some $n$ than $Z(S_n) = \{e\}$. We want to show that $Z(S_{n+1}) = \{ e \} $. Let $\sigma \in S_{n+1}$ be some non-identity permutation. If $\sigma \in S_n$ then $\sigma$ is not in the center by the induction hypothesis. Therefore assume $\sigma \not\in S_n$, so $\sigma$ does not leave $n+1$ fixed (here I am identifying $S_{n+1}$ with the symmetry group of the set $\{ 1, 2, \ldots , n+1\}$). Now let $a = \sigma(n+1)$ and let $b$ be some element of $\{ 1, 2, \ldots , n+1\}$ not equal to $a$, which is possible (why can we choose $b$ like this?). Let $\tau = (ab)$. Then:
$$ \tau\sigma(n+1) = \tau(a) = b $$
$$ \sigma\tau(n+1) = \sigma(n+1) = a $$
$$ a \neq b $$
This implies $\sigma\tau \neq \tau\sigma$ (why?). Hence for any $\sigma$ we can choose some $\tau$ which does not commute with it.  

This is essentially a proof which does not rely on induction, just replace $n+1$ by some element not fixed by $\sigma$, which is possible if $\sigma \neq e$. 
A: This answer might be a tad off-topic since it doesn't help with your induction proof, but depending on the results you have, you can make the proof quite easy on yourself.  There are multiple ways of going about this without induction, and this might not be the best.  However, it's useful to read and understand for pedagogical purposes.
If you already know that $A_n$ is the only (nontrivial) proper normal subgroup of $S_n$ for all $n \geq 5$, then you just need to convince yourself that $Z(S_n) \neq A_n$ since the center of a group is always a normal subgroup.  In particular, it's easy to find even a single element of $A_n$ that does not commute with every element of $S_n$.  
After that, you just need to worry about $S_3$ (which is exceedingly simple either working directly or applying that $G/Z(G)$ cyclic $\implies G$ abelian) and $S_4$ (which takes just a little more work).
A: Just because you want to prove a family of statements parametrized by $n$ doesn't mean that the statement for $n+1$ depends directly on the statement for $n$. I'm not sure how natural induction is here, although I could be wrong. Below is the proof approach that appeals to me.
Here are some thoughts to help you start. Two elements of a group $\pi,\sigma\in G$ commute if $\sigma\pi=\pi\sigma$, but this is easily seen to be equivalent to $\sigma\pi\sigma^{-1}=\pi$. So what does conjugation do to a permutation, how does it change how it looks? One of the default ways to represent permutations is with disjoint cycle notation, the building blocks of which are cycles. Every permutation is a product of disjoint cycles. For $m$-cycles, conjugating it changes it like so:
$$\sigma(a_1~a_2~\cdots~a_m)\sigma^{-1}=(\sigma(a_1)~\sigma(a_2)~\cdots~\sigma(a_m)).$$
Given an arbitrary $\pi\in S_n$ (which is not the identity) (with $n\ge3$) you want to be able to find or make a permutation $\sigma$ so that $\sigma\pi\sigma^{-1}\ne\pi$. Use $\pi$'s disjoint cycle representation to do this.
Note that reasoning with the disjoint cycle representation also plays a part in the elementary proof that alternating groups are the only nontrivial proper normal subgroups of symmetric groups.
