Is it possible to reformulate the expression
$$ (1+\sqrt{x})^n + (1-\sqrt{x})^n $$
in the form that contains no square roots of $x$ and no iterative sums (i.e. can be computed in constant time)?
Note that $(1+\sqrt{x})^n + (1-\sqrt{x})^n = \sum_{k>0}\binom{n}{2k}x^{k}$ which proves that it produces only integer solutions for integer $x$ and $n$. This means that I have either $\sqrt{x}$ or iterative summation. Can one get rid of both in the same expression?