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 ?
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$.
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.