Deriving a relation for the frobenius norm should be easy.
Define $x_n=[k_1,k_2,\dots,k_n]^{T}$, then it is straight forward to see that $||A_n||_{F}^{2}=(n-1)||x_n||^2_{2}$. Using this recursive formula, one can derive that $||A_{n+1}||_{F}^{2}=||A_{n}||_{F}^{2}+||x_{n+1}||^2_{2}+(n-1)|k_{n+1}|^{2}$.
Deriving the induced norm case is slightly more involved. But may be this direction can help.
Define the matrix $T_n=ones(N,N)-I$ where $ones(N,N)$ is a $N \times N$ matrix with all entries as one and $I$ is the identity matrix. To get a feel of it, for $N=4$,
\begin{align}
T_4=\left[ \begin{array}{cccc} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array} \right]
\end{align}
Define $D_n=diag(x_n)$ where $x_n$ is defined as earlier and $D_n$ is the diagonal matrix with $x_n$ as its diagonal entries. Note that now your matrix $A_n$ is
$A_n=T_nD_n$
Note the observation that the singular values of $T_n$ are $(n-1,1,\dots,1)$. Consider the problem.
\begin{align}
\max_{||D_{n}^{-1}y||=1} ||T_ny||_{2}
\end{align}
I am not sure how exactly you can solve this. Once you can solve that deriving a relation between successive induced norms should be a easy matter.