Induction Proof

tukeywilliams · #1 $Old$ June 7th, 2007, 03:24 AM

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

Pterid · #2 $Old$ June 7th, 2007, 04:26 AM

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.

In your case:

$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!

tukeywilliams · #3 $Old$ June 7th, 2007, 04:33 AM

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

Thanks a lot.

Pterid · #4 $Old$ June 7th, 2007, 04:36 AM

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

ThePerfectHacker · #5 $Old$ June 7th, 2007, 08:23 AM

Quote:

Originally Posted by tukeywilliams $View Post$

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$ .