The claim is true.

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.  Moreover the spectrum of $A$ contains $2$ and $-2$ as the limits $\|(2+A)^ne_0\|^{1/n}$ and $\|(2-A)^ne_0\|^{1/n}$ are both $4$ by Stirlings type estimates. (In fact, for each $n$ the quantities are equal. This says that the spectral radius of the operators $2+A, 2-A$ are equal to $4.$)

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) =\infty.$
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.$ (Moreover, it will only change by one eigenvalue.)

So, now we consider the spectrum of $4\alpha +A$ and compare it to $4\alpha+A + \alpha P.$ If $\alpha >0,$ the extra eigenvalue of $A+\alpha P$ appears when $F_A(z) = -1/\alpha$ which happens to the right of the spectrum, and therefore the norm increases. Similarly, the norm increases in the other case.

Note that it is not true for a general $\alpha + A + \beta P,$ and has a somewhat subtle dependence on your choice of problem.