Answer: 18

I'll give an easy solution (provided by Bugz, Challenger46, Daniel Whitman, lee, Tom, venkatesh, Sasha, and Bala)

All of these were more or less equivalent, but Sasha's was the neatest, so here it is:

Let u=2^{x}

u^{2} + u^{-2} = 7

u^{2} + 2 + u^{-2} = 9 = (u + u^{-1})^{2}

u + u^{-1} = 3

u^{3} + u^{-3} = (u + u^{-1})(u^{2} - 1

+ u^{-2}) = (3)(7-1) = 18

My solution was needlessly complex, but (I thought) interesting, so I wrote it up in great detail in a web page -- Write Up -- but here it is in a nutshell:

Let y=2^{x}. Then y^{2}+y^{-2}=7, so y^{4}-7y^{2}+1=0.

Solving the quadratic in y^{2}, we get y^{2} = 7/2 ± sqrt(45)/2

This presents a tricky problem in itself: we can express y^{2} in the form a+sqrt(b), where a and b are rational, but can y be expressed in this form? See Simplifying Nested Radicals for the full explanation, but very briefly, the answer is usually no, but in this case (because the puzzle was contrived, I'm sure) the answer is yes. There are four solutions in y, but two of them are negative, so we can throw them out (because y=2^{x} must be positive for any real x) leaving us with:

y=3/2 ± sqrt(5)/2

The quadratic that has these roots can be obtained by multiplying (y-r_{1})(y-r_{2}), where r_{1} and r_{2} are the two roots.

In this way, we discover that these are the roots of the polynomial y^{2}-3y+1=0, which is interesting because its coefficients are

palindromic (if that's not a word it should be).

For one thing, this means the two roots are reciprocals of one another, so pick either one, and the value of y^{n}+y^{-n} will be the same.

For another thing, this means the recurrence relation that describes the sequence of successive powers of y runs the same way in both directions!

Consider the sequence y^{0}, y^{1}, y^{2}, … where y is a root of ay^{2}+by+c=0

y^{n} = -(b/a)y^{n-1} - (c/a)y^{n-2}, so each element can be obtained from this linear combination of the previous two.

Similarly,

y^{n} = -(b/c)y^{n+1} - (a/c)y^{n+2}, so each element can be obtained from this linear combination of the *following* two.

In this case, the coefficients of the polynomial are symmetrical, 1, -3, 1, so each element is equal to three times the previous one minus the one before that, OR three times the * next* one minus the one * after* that.

This symmetry is important, because it means that y^{n} + y^{-n} = 3(y^{n+1} + y^{-n-1}) - (y^{n+2} + y^{-n-2})

Knowing this recurrence relation and any two elements in the sequence will allow us to solve the entire sequence.

We know y^{2}+y^{-2} = 7, and it's obvious that y^{0}+y^{-0} = 2, so from the recurrence relation (each element is three times the previous/next element minus the element before/after that) it follows that y^{1}+y^{-1} = 3.

The rest of the sequence follows: 2, 3, 7, 18, 47, 123, 322, 843, 2207, 5778, …