2

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?

dmytro
  • 352
  • Well, do you know the answer for just $\sum \binom nlx^l$? – Grigory M Jan 17 '15 at 19:36
  • @GrigoryM I can only see how that helps for the even terms – Trajan Jan 17 '15 at 19:43
  • @1234 $\frac{P(x)+P(-x)}2$ extracts even terms from any polynomial $P$, you know... – Grigory M Jan 17 '15 at 19:44
  • @GrigoryM. Yepp, it's (1-x)^n. Actually this question appeared when I was trying to simplify (1+x)^n + (1-x)^n. In my case, x is $\sqrt{5}$. The expression above proves that it has only integer solutions. Now I have a strong feeling that it can be simplified somehow – dmytro Jan 17 '15 at 19:46
  • @GrigoryM Thats the step I was missing – Trajan Jan 17 '15 at 19:46
  • PS: this is not a homework, so don't hesitate to give direct answers. I'm just trying to simplify (1+x)^n+(1-x)^n here – dmytro Jan 17 '15 at 19:51
  • @dmytro It seems, from comments, like you've thought a bit more about the question than indicated in the question's body. It might be wise to include some of the related identities you are aware of in the question body - you'd be more likely to get a good answer (and avoid downvotes/close votes) if you do. – Milo Brandt Jan 17 '15 at 20:00
  • @Meelo Thanks, that's a good point. I've updated the question – dmytro Jan 17 '15 at 20:01
  • You ask for a form for your sum, "containing no sums". $(1+x)^n+(1-x)^n$ is (pretty much) the answer to your question. But you then reveal in the comments that you know about $(1+x)^n+(1-x)^n$, and you are trying to simplify it. If that's what you are trying to do, then you should edit your question so that's what you ask. But I'd say that formula is about as simple as it's going to get. But then it appears that all you really want is the value of that expression at $x=\sqrt5$. – Gerry Myerson Jan 17 '15 at 20:01
  • So I suggest you go away, figure out what it is that you really want to know, and then come back and ask the question you really want to ask. – Gerry Myerson Jan 17 '15 at 20:02
  • OK, you have edited the question so you are asking for a formula with no odd powers of $x$. But you have such a formula --- the original summation you started out with has no odd powers of $x$. So, what do you want? Maybe you are best off looking for a simple linear recurrence satisfied by the sequence --- that may be enough to show that the terms are integers. – Gerry Myerson Jan 17 '15 at 20:04
  • @GerryMyerson, I'm looking for a solution involving only even powers of $x$ (like in the iterative version), yet without sums. If there's no such solution, then it would be cool to prove this somehow – dmytro Jan 17 '15 at 20:06
  • @GerryMyerson It just seems odd to me that an analytical expression ($(1-\sqrt{x})^n+(1+\sqrt{x})^n$) spitting out only integers for integer $x$ still relies on computing $\sqrt{x}$ inside the function – dmytro Jan 17 '15 at 20:08
  • The problem is, you don't knowe what you mean by "a solution". But do consider the recurrence $u_n-2u_{n-1}+(1-k)u_{n-2}=0$. – Gerry Myerson Jan 17 '15 at 20:09
  • 1
    @dmytro This is not an unusual phenomenon. $e^{\ln x}$, $\cos(\pi x)$, etc. – Matt Samuel Jan 17 '15 at 20:09
  • 1
    Your analytical expression, dmytro, is a symmetric function in the conjugates of $\sqrt x$, hence, an integer. Galois Theory explains this beautifully. You will enjoy it greatly when you get there. – Gerry Myerson Jan 17 '15 at 20:11
  • @GerryMyerson Alright, thanks, I'll try to get into this. So, what you're saying is that there's no way to get analytical form of $(1+\sqrt{x})^n+(1-\sqrt{x})^n$ involving no square roots of $x$. Am I correct? If so, I would accept this as an answer, if you posted it as such. – dmytro Jan 17 '15 at 20:15
  • The question isn't well-posed, until you can give a precise definition of what you mean by "analytical form". – Gerry Myerson Jan 17 '15 at 20:18
  • @GerryMyerson I have updated the question. See if it is clearer now – dmytro Jan 17 '15 at 20:28

0 Answers0