1. ## Induction Proof

For a real number $\displaystyle x$ suppose that $\displaystyle x + \frac{1}{x}$ is an integer. Prove that $\displaystyle x^{n} + \frac{1}{x^{n}}$ is an integer for all positive integers $\displaystyle n$.

Here is what I did:

Proof: We use induction on $\displaystyle n$. Base case: $\displaystyle x^{1} + \frac{1}{x^{1}}$ is an integer. Inductive step: Suppose that $\displaystyle x^{k} + \frac{1}{x^{k}}$ is an integer for some positive $\displaystyle k$. Then $\displaystyle \left(x^{k} + \frac{1}{x^{k}}\right)\left(x+\frac{1}{x}\right) = \frac{x^{k+2}+x^{k}+x^{2-k}+x^{-k}}{x}$ $\displaystyle = x^{k+1} + x^{k-1} + x^{-k+1} + x^{-k-1}$ $\displaystyle = \left(x^{k+1} + \frac{1}{x^{k+1}}\right) + \left(x^{k-1} + \frac{1}{x^{k-1}}\right)$ (which is an integer by induction hypothesis because an integer multiplied by an integer is an integer). From here, how would I show that $\displaystyle x^{k+1} + \frac{1}{x^{k+1}}$ is an integer?

Thanks

2. You're nearly there - in fact, you've pretty much proved it!

You just need to use an alternative kind of induction, called course of values induction. It works along these lines:
• Say $\displaystyle P(n)$ is the statement you need to prove for all n.
• Base case: Show $\displaystyle P(1)$.
• Induction step: Assume $\displaystyle P(j)$ is true for ALL $\displaystyle j \leq k$; then show $\displaystyle P(k+1)$.
This assumes more, but it's a perfectly valid way to do induction.

$\displaystyle P(n) : \left[ x^n + \frac{1}{x^n}\text{ is an integer} \right]$

The base case has been given already.

For the inductive step, you rightly considered the expression

$\displaystyle \left( x^k + \frac{1}{x^k} \right) \left( x^1 + \frac{1}{x} \right) \equiv \left( x^{k+1} + \frac{1}{x^{k+1}} \right) + \left( x^{k-1} + \frac{1}{x^{k-1}} \right)$

You know the LHS is an integer, and by course of values induction, $\displaystyle \left( x^{k-1} + \frac{1}{x^{k-1}} \right)$ is an integer.

(We can assume $\displaystyle P(k-1)$, as well as $\displaystyle P(k)$!)

Hence, $\displaystyle \left( x^{k+1} + \frac{1}{x^{k+1}} \right)$ is an integer, as on the RHS, integer + integer = integer.

QED!

3. aaahhh, that was what I was thinking. I needed to use strong induction right?

Thanks a lot.

4. Yeah, it's also known as strong induction or 'complete induction', apparently.

5. Originally Posted by tukeywilliams
For a real number $\displaystyle x$ suppose that $\displaystyle x + \frac{1}{x}$ is an integer. Prove that $\displaystyle x^{n} + \frac{1}{x^{n}}$ is an integer for all positive integers $\displaystyle n$.

Here is what I did:

Proof: We use induction on $\displaystyle n$. Base case: $\displaystyle x^{1} + \frac{1}{x^{1}}$ is an integer. Inductive step: Suppose that $\displaystyle x^{k} + \frac{1}{x^{k}}$ is an integer for some positive $\displaystyle k$. Then $\displaystyle \left(x^{k} + \frac{1}{x^{k}}\right)\left(x+\frac{1}{x}\right) = \frac{x^{k+2}+x^{k}+x^{2-k}+x^{-k}}{x}$ $\displaystyle = x^{k+1} + x^{k-1} + x^{-k+1} + x^{-k-1}$ $\displaystyle = \left(x^{k+1} + \frac{1}{x^{k+1}}\right) + \left(x^{k-1} + \frac{1}{x^{k-1}}\right)$ (which is an integer by induction hypothesis because an integer multiplied by an integer is an integer). From here, how would I show that $\displaystyle x^{k+1} + \frac{1}{x^{k+1}}$ is an integer?

Thanks
The problem of the week!

Yes, the trick here is the ordinary induction does not work. You need to use strong induction.
----
Another way to do this, which is longer, but much more fun.
Isto consider the Binomial expansion of:
$\displaystyle \left( x + \frac{1}{x} \right)^n$

This is more fun because then you need to consider even and odd $\displaystyle n$ and you take advantage of all $\displaystyle 1,2,3,...,n$ cases. Unlike here where you just use $\displaystyle n-1$.