  An element $\alpha \in \mathbb{F}_{q^n}$ is normal over $\mathbb{F}_q$ if
$\mathcal{B}=\{\alpha, \alpha^q, \alpha^{q^2}, \cdots, \alpha^{q^{n-1}}\}$
forms a basis of $\mathbb{F}_{q^n}$ as a vector space over $\mathbb{F}_q$. It
is well known that $\alpha \in \mathbb{F}_{q^n}$ is normal over $\mathbb{F}_q$
if and only if $g_{\alpha}(x)=\alpha x^{n-1}+\alpha^q x^{n-2}+ \cdots +
\alpha^{q^{n-2}}x+\alpha^{q^{n-1}}$ and $x^n-1$ are relatively prime over
$\mathbb{F}_{q^n}$, that is, the degree of their greatest common divisor in
$\mathbb{F}_{q^n}[x]$ is $0$. Using this equivalence, the notion of $k$-normal
elements was introduced in Huczynska et al. ($2013$): an element $\alpha \in
\mathbb{F}_{q^n}$ is $k$-normal over $\mathbb{F}_q$ if the greatest common
divisor of the polynomials $g_{\alpha}[x]$ and $x^n-1$ in $\mathbb{F}_{q^n}[x]$
has degree $k$; so an element which is normal in the usual sense is $0$-normal.
  Huczynska et al. made the question about the pairs $(n,k)$ for which there
exist primitive $k$-normal elements in $\mathbb{F}_{q^n}$ over $\mathbb{F}_q$
and they got a partial result for the case $k=1$, and later Reis and Thomson
($2018$) completed this case. The Primitive Normal Basis Theorem solves the
case $k=0$. In this paper, we solve completely the case $k=2$ using estimates
for Gauss sum and the use of the computer, we also obtain a new condition for
the existence of $k$-normal elements in $\mathbb{F}_{q^n}$.
