# Homework Help: Induction: prove x^n + 1/x^n = 2cos(n*theta)

1. Sep 4, 2012

### ptolema

1. The problem statement, all variables and given/known data

If a and theta are real numbers such that x + 1/x = 2cos(theta), then:

x^n +1/x^n = 2cos(n*theta)

2. Relevant equations

x + 1/x = 2cos(theta)

3. The attempt at a solution

So I was able to show that the statement was true for n=1, but I'm stuck on how to even start proving it for n+1. I tried x^(n+1) + 1/x^(n+1), thinking I could solve it for n+1, but to no avail. Help, please?

2. Sep 4, 2012

### Simon Bridge

IF
$x^2 + 1 = 2x\cos(\theta)$ ...(1)

THEN
$x^{2n}+1 = 2x^k\cos(n\theta)$ ...(2)

by induction:

n=1: $x^2 + 1 = 2x\cos(\theta)$ ... this is just (1) so true.

from pythagoras and trig relations - this also means:
$\sqrt{4x^2-(x^2+1)^2} = 2x\sin(\theta) = (x^2+1)\tan(\theta)$

n=k: $x^{2k}+1 = 2x^k\cos(k\theta)$ ...(3) assumed true.

consequences from pythagoras and trig?

n=k+1: $x^{2k+2}+1 = 2x^{k+1}\cos(k\theta+\theta)$

This is as far as you've got ... could see what happens if you use the difference in angles identity on the cosine ($\cos(A+B)=\cdots$)

You are going to have to do a lot of messing about before you'll see what to do: builds character ;)

3. Sep 4, 2012

### csopi

The trick is that $$x=\cos \theta + i\cdot \sin\theta$$, so
$$x^n+x^{-n}=\cos n\theta+i\sin n\theta+cos n\theta-i\sin n\theta=2\cos n\theta$$

4. Sep 4, 2012

### Kolmin

My two cents...
Part of the problem is related to the way in which you framed it. To make induction work, you should put it following this structure (assuming that P is whatever property):

$\forall n \in N ( P(n) \rightarrow P(n+1) )$.

The key is that you assume P(n), and then move from that to prove P(n+1).
Basing on how you framed it, you cannot do it: instead, you have to prove P(n).

5. Sep 4, 2012

### Mute

I'm guessing the point might be to prove the statement without resorting to complex analysis, which is what DeMoivre originally had to do.

Anyways, OP, to solve this by induction, the first thing you have to do is show the base case. Since n =1 is what defines x, you probably have to take n = 2 as the base case.

Then, you assume that

$$x^n + x^{-n} = 2\cos(n\theta)$$

is true. Let me call this the base equation. You want to show that it implies

$$x^{n+1} + x^{-n-1} = 2\cos((n+1)\theta).$$

I didn't do this myself yet, but my first guess at an approach would be to try to get an $x^{n+1}$ into the base equation, perhaps by multiplying through by x. This obviously doesn't get you the equation you need to prove - there's no $x^{-n-1}$. You could alternately multiply the base equation through by 1/x, and end up with an equation that's missing the $x^{n+1}$ term. I'll let you figure out where to go from here. Remember that you are taking the base equation to be true by assumption, for any positive power $\leq n$.

6. Sep 5, 2012

### uart

Has anyone noticed that in the base problem the values of $x$ and $\theta$ are not at all arbitrary real numbers?

Since $| x + \frac{1}{x} | \ge 2$ then the only possible values are $x = \pm 1$, and the corresponding values of $\theta = 2k \pi$, $(2k+1) \pi$.

It seems to make the whole proof a bit moot, seeing as you can just substitute in the known values to verify the general proposition directly.

7. Sep 10, 2012

### Simon Bridge

You mean since $1 \leq \cos(\theta) \leq 1$, the equation is only valid for $-2 \leq x+\frac{1}{x} \leq 2$ ... ?

Presumably the exercise is not to prove the statement but to practice the method. Admittedly there are probably better examples...

8. Sep 10, 2012

### uart

No I mean that considering just the function "$x + 1/x$" in isolation, we can only only have either $x+\frac{1}{x} \leq -2$ or $x+\frac{1}{x} \geq 2$. So when we include the range restriction of $\cos(\theta)$, we end up with only two possible values of "x". That is, $x = 1$ or $x = -1$.

Last edited: Sep 10, 2012
9. Sep 10, 2012

### Simon Bridge

Yes - sorry: since you'd already said that, I left it to context. I just filled in the other half.

I should have been more exact: here, let me practice:

Since, in the RHS, the cosine must be in [-1,1], then the LHS (x+1/x) must be in [-2,2] ... but LHS is not in (-2,2), therefore, there are only two values for x which can possibly make the relation true: x+1/x = {-2,2} i.e. x = {-1,1} (being a bit loose with the equals sign here).

I had noticed that the relation could only be true for specific values but had not bothered to calculate them. It is not that uncommon to give students an exercise which could be completed more easily by another method... mountaineers may climb a peak by a route other than the easiest one too ;)