# Edited:what is a way to solve this problem other than use algebra way?

I am getting tired of using expansion to solve this problem. I wonder if there is any non-algebra ways to solving it.

Problem: Suppose that the number $x$ satisfies the equation $x+x^{-1}=3$. Compute the value of $x^7+x^{-7}$.

-
I would just square it three times with the binomial formula (extracting the constant term out every time). I am quite a bit older than you are, and that doesn't make me tired :-). Mind you, I would call that an algebraic way as well. What did you want to do? Use the formula for solving the quadratic, and then raise the expressions involving radicals to eighth power? Ok, that might be tiring, but also an ugly way of going about this. – Jyrki Lahtonen Oct 20 '11 at 21:11
The problem is an algebra problem. Let's solve it efficiently. Square. We get $x^2+2+x^{-2}=9$, so $x^2+x^{-2}=7$. Square again. We get $x^4 + 2+x^{-4}=49$, so $x^4+x^{-4}=47$. Square again. We get $x^8+x^{-8}=47^2-2=2207$. – André Nicolas Oct 20 '11 at 21:18
Write $P_n=x^n+x^{-n}$. Show first that $P_nP_1=P_{n+1}+P_{n-1}$. You can also try cubing, and see what happens. Have fun! That's what contest-math is about :-) – Jyrki Lahtonen Oct 20 '11 at 21:26
@Victor It would have been nice of you to describe your approach in the question as opposed to saying that you are tired of using an approach that we may or may not guess. Show some effort, and you will get upvotes on your question even if your attempt didn't lead to the finish line! – Jyrki Lahtonen Oct 20 '11 at 21:35
@Victor: If after an answer has been posted, you want to ask a modified question, your new question should be either in a new post, or added to the existing question. So the question about $x^8+x^{-8}$ should have been kept, with the question about $x^7+x^{-7}$ added. Removing the $x^8+x^{-8}$ stuff puts people who answered that question in the awkward position of having to delete or modify answers, or to leave answers that no longer appear to be relevant. – André Nicolas Oct 20 '11 at 22:08

Here is another way which uses the Lucas Numbers:

We can rearrange the equality $x^{-1}+x=3$ to get the polynomial $x^2-3x+1=0$. Notice that the only solutions are $x=\phi^2$ and $x=\phi^{-2}$ where $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio. (In particular one root is $\frac{3+\sqrt{5}}{2}=\left(\frac{1+\sqrt{5}}{2}\right)^2$)

Since for either choice $x=\phi^2$ or $x=\phi^{-2}$, the quantity $x^n+x^{-n}$ is the same, we can write $$x^n+x^{-n}=\phi^{2n}+\phi^{-2n}.$$ This above sum has a particular name, and is known as the $2n^{th}$ Lucas Number. It can be described by a recurrence relation like the Fibonacci numbers. In particular we have that $$L_n=\phi^n+\phi^{-n}.$$ For example this gives us that $$x^{8}+x^{-8}=L_{16}=2207.$$ Similarly $$x^{-7}+x^7=L_{14}=843.$$

-

Edit: The original question asked to evaluate $x^8+x^{-8}$, but was edited by the OP after this answer was composed.

I am not sure if this counts as a new way, but notice that in general $$\left(u^{-1}+u\right)^2=u^{-2}+u^2+2.$$

This means that from the first equation we can read off $$u^{-2}+u^2 =9^2-2=7$$ and then $$u^{-4}+u^4 =7^2-2=47$$ and lastly $$u^{-8}+u^8 =47^2-2=2207.$$

Remark: This was actually the key idea in the solution to B4 on the putnam in 1995. Specifically that problem was

B4: Evaluate $$\left(2207-\frac{1}{2207-\frac{1}{2207-\cdots}}\right)^{\frac{1}{8}}$$ and write your answer in the form $\frac{a+b\sqrt{c}}{d}$ where $a,b,c,d$ are integers.

The solution is given by letting $x$ equal the above quantity. Taking 8th powers and rearranging, we notice that $$x^8+x^{-8}=2207.$$ From here we do the reverse of my above steps to conclude $x$ is one of the roots of $x+x^{-1}=3$. (Or in other words, the golden ratio squared)

-

Ok. Hint for the original question about $x^8+x^{-8}$: $$x^2+2+\frac1{x^2}=(x+\frac1x)^2=3^2=9 \Rightarrow x^2+\frac1{x^2}=7.$$ $$x^4+2+\frac1{x^4}=(x^2+\frac1{x^2})^2=7^2=49 \Rightarrow \ldots$$

-