1. ## Induction Proof

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

Here is what I did:

Proof: We use induction on $n$. Base case: $x^{1} + \frac{1}{x^{1}}$ is an integer. Inductive step: Suppose that $x^{k} + \frac{1}{x^{k}}$ is an integer for some positive $k$. Then $\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}$ $= x^{k+1} + x^{k-1} + x^{-k+1} + x^{-k-1}$ $= \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 $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 $P(n)$ is the statement you need to prove for all n.
• Base case: Show $P(1)$.
• Induction step: Assume $P(j)$ is true for ALL $j \leq k$; then show $P(k+1)$.
This assumes more, but it's a perfectly valid way to do induction.

$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

$\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, $\left( x^{k-1} + \frac{1}{x^{k-1}} \right)$ is an integer.

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

Hence, $\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 $x$ suppose that $x + \frac{1}{x}$ is an integer. Prove that $x^{n} + \frac{1}{x^{n}}$ is an integer for all positive integers $n$.

Here is what I did:

Proof: We use induction on $n$. Base case: $x^{1} + \frac{1}{x^{1}}$ is an integer. Inductive step: Suppose that $x^{k} + \frac{1}{x^{k}}$ is an integer for some positive $k$. Then $\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}$ $= x^{k+1} + x^{k-1} + x^{-k+1} + x^{-k-1}$ $= \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 $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:
$\left( x + \frac{1}{x} \right)^n$

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