I want to prove that $$A^{(p)} = \begin{pmatrix} a & 1 & 1 & \dots & 1 & 1 & 1 \\ 1 & a & 1 & \dots & 1 & 1 & 1 \\ 1 & 1 & a & \dots & 1 & 1 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 1 & 1 & 1 & \dots & 1 & a & 1 \\ 1 & 1 & 1 & \dots & 1 & 1 & a \end{pmatrix} \in\mathbb{R}^{p\times p}$$
has eigenvalues $\lambda_+=a+p-1$ and $\lambda_-=a-1$ with degeneracy $p-1$ by using mathematical induction. Evidence that these eigenvalues could be correct were found 'empiricaly' by Mathematica.
Induction Base Case $(p=2)$
$$\det(A^{(2)}-\lambda E_2) = \det\begin{pmatrix}a-\lambda & 1\\1 & a-\lambda\end{pmatrix} =(\lambda-(a-1))(\lambda-(a+1)) $$
Induction Hypothesis $(p\in\mathbb{N})$
$$\det(A^{(p)}-\lambda E_p) =(\lambda-(a-1))^{p-1}(\lambda-(a+p-1))$$
Induction Step $(p\to p+1)$
$$\det(A^{(p+1)}-\lambda E_{p+1}) = \det\begin{pmatrix} a-\lambda & 1 & 1 & \dots & 1 & 1 & 1 \\ 1 & a-\lambda & 1 & \dots & 1 & 1 & 1 \\ 1 & 1 & a-\lambda & \dots & 1 & 1 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 1 & 1 & 1 & \dots & 1 & a-\lambda & 1 \\ 1 & 1 & 1 & \dots & 1 & 1 & a-\lambda \end{pmatrix}$$
We can subtract the last row from the first row $$\det\begin{pmatrix} a-\lambda-1 & 0 & 0 & \dots & 0 & 0 & 1-a+\lambda \\ 1 & a-\lambda & 1 & \dots & 1 & 1 & 1 \\ 1 & 1 & a-\lambda & \dots & 1 & 1 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 1 & 1 & 1 & \dots & 1 & a-\lambda & 1 \\ 1 & 1 & 1 & \dots & 1 & 1 & a-\lambda \end{pmatrix}$$ and apply Laplace's formula to the first row. The first entry (upper left corner) gives $$(a-\lambda-1) \det\begin{pmatrix} a-\lambda & 1 & \dots & 1 & 1 & 1 \\ 1 & a-\lambda & \dots & 1 & 1 & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 1 & 1 & \dots & 1 & a-\lambda & 1 \\ 1 & 1 & \dots & 1 & 1 & a-\lambda \end{pmatrix}$$ which is just the case of our induction hypothesis, thus $$-(\lambda-(a-1))^p(\lambda-(a+p-1)) $$ is the first contribution to Laplace's formula. The second contribution reads $$(1-a+\lambda) (-1)^{p+2} \det\begin{pmatrix} 1 & a-\lambda & 1 & \dots & 1 & 1 \\ 1 & 1 & a-\lambda & \dots & 1 & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & 1 & 1 & \dots & 1 & a-\lambda\\ 1 & 1 & 1 & \dots & 1 & 1 \end{pmatrix}$$ and we can subtract the first column from all other columns yielding $$\det\begin{pmatrix} 0 & a-\lambda-1 & 0 & \dots & 0 & 0 \\ 0 & 0 & a-\lambda-1 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & \dots & 0 & a-\lambda-1\\ 1 & 1 & 1 & \dots & 1 & 1 \end{pmatrix}$$ on which we can reapply Laplace's formula and use that the determinant of a diagonal matrix equals the product of the diagonal entries, hence $$(-1)^{p+1}(\lambda-(a-1))^{p+1} $$ is the second contribution to the first application of Laplace's formula. Now combining both I find $$\det(A^{(p+1)}-\lambda E_{p+1}) = (-1)(\lambda-(a-1))^p(\lambda-(a+p-1))+(-1)^{p+1}(\lambda-(a-1))^{p+1} =(-1)(\lambda-(a-1))^p(\lambda-a-p+1+(-1)^p(\lambda-a+1)) $$ which seems faulty: on the one hand side the factor $(-1)^{p}$ should not exist as for odd $p$ the characteristic polynomial should varnish which has been shown to be not the case for i.e. $p=3$ (see Mathematica). On the other hand even if that factor would be wrong the final expression would yield $$(-2)(\lambda-(a-1))^p(\lambda-(a-p/2+1))$$ which would contradict the induction hypothesis.
Did I made a mistake in evaluating the determinant or is the induction hypothesis wrong?
This is an answer not by induction, in response to a comment/answer by OP. $$ \newcommand{\bu}{ {\mathbf u}} \newcommand{\bv}{ {\mathbf v}} \newcommand{\bM}{ {\mathbf M}} \newcommand{\bI}{ {\mathbf I}} \newcommand{\bU}{ {\mathbf U}} \newcommand{\bQ}{ {\mathbf Q}} $$ Your matrix $\bM$ is $$ \bM = \bU + (a-1)\bI $$ where $\bU$ is a matrix of all $1$s. It's clear that $$ (n-1) + a $$ is an eigenvalue, for the vector $\bu'$ consisting of all $1$s is a corresponding eigenvector. We can normalize this to a vector $\bu$ consisting of all $\frac{1}{\sqrt{n}}$ entries. Furthermore, we can write $\bU$ as $n \bu \bu^t$, which shows that $U$ has rank $1$, which is no surprise, because all its columns are the same.
Now let $\bv_1, \ldots, \bv_{n-1}$ be an orthonormal basis for the space $$ H = \{ \bv \mid \bu \cdot \bv = \bu^t \bv = 0 \} $$ of vectors orthogonal to $\bu$. Let's compute $\bM\bv_i$ for any one of these. It's \begin{align} \bM\bv_i &= ( \bU + (a-1)\bI ) \bv_i \\ &= ( n\bu \bu^t + (a-1)\bI ) \bv_i \\ &= (n\bu \bu^t) \bv_i + (a-1)\bI \bv_i \\ &= n\bu (\bu^t \bv_i) + (a-1)\bv_i \\ &= n\bu (0) + (a-1)\bv_i \\ &= (a-1)\bv_i \\ \end{align} In other words, each of the vectors $\bv_i$ is an eigenvector of eigenvalue $a-1$.
So the vectors $\{\bu, \bv_1, \bv_2, \ldots, \bv_{n-1}\}$ constitute an orthonormal set of eigenvectors of $\bM$, and if we form a matrix $\bQ$ with those as its columns, we get $$ \bQ^t \bM \bQ = \pmatrix{(n-1)+ a & & & & & \\ & a-1 & & & & \\ & & a-1 & & & \\ & & & \ldots& & \\ & & & & a-1 & \\ & & & & & a-1} $$ which is pretty much a complete eigenanalysis of $\bM$.