The claim is false.

Any difference in norm must be picked up on the span of $(T_s+T_t)^ne_0.$ So we will apply perturbation theory on that subspace. The value of $\langle(T_s+T_t)^ne_0,e_0\rangle$ should be ${n}\choose{n/2}$ when $n$ is even and zero otherwise. Note that $A=T_s + T_t$ is self-adjoint.

Consider the function
$$F_A(z) = \langle (T_s+T_t-z)^{-1}e_0,e_0 \rangle.$$
The places where $F_A$ analytically continues through $\mathbb{R}$ is exactly the complement of the spectrum.
Now consider $\lim_{z\rightarrow 2^+} F_A(z)$ and $\lim_{z\rightarrow -2^-} F_A(z).$ 
Apparently, $\lim_{z\rightarrow 2^+} F_A(z)= -\infty.$
Also, using Stirling's formula type estimates,
$\lim_{z\rightarrow -2^-} F_A(z)\approx \frac{1}{2}\sum \frac{(-1)^k}{\sqrt{\pi n}}.$
By the Aronszajn-Krein formula, the spectrum of 
$A + \alpha P$ is governed by $F_{A+\alpha P}=\frac{F}{1+\alpha F}.$ Note the spectrum will only change if $F(z) = -\frac{1}{\alpha}$ has a real solution in the complement of the spectrum of $A.$ As one of the limits is non-infinite, there is an $\alpha$ such that the spectrum is preserved.