1. ## Strong induction

Hi,

I have this proof that I can't find. I have to use strong induction but I don't know how to use it in this case.

Suppose x is a real number, $x \neq 0$ and $x+1/x$ is an integer. Prove by strong induction that for all n ≥ 1, $x^n +1/x^n$ is an integer.

Could someone help me?

2. Originally Posted by TheFangel
Hi,

I have this proof that I can't find. I have to use strong induction but I don't know how to use it in this case.

Suppose x is a real number, $x \neq 0$ and $x+1/x$ is an integer. Prove by strong induction that for all n ≥ 1, $x^n +1/x^n$ is an integer.

Could someone help me?
The base case $n=1$ is true by assumption, now assume that for some $k$ we have $x^j+x^{-j}$ is an integer for all $j \le k$.

Now consider:

$X_{k+1}=\left(x+\frac{1}{x}\right)^{k+1}$

if you examine the expansion you will find that pairs of terms can be grouped together to give integers by the induction hypothesis (with possibly an unpaired middle term which will be an integer on its own) except for the first and last terms which together are:

$u_{k+1}=x^{k+1}+\frac{1}{x^{k+1}}$

Hence as $X_{k+1}$ is an integer as are all the other terms by the induction hypothesis so is $$u_{k+1}$$ and so the proof follows by strong induction.

CB

3. Originally Posted by CaptainBlack
The base case $n=1$ is true by assumption, now assume that for some $k$ we have $x^j+x^{-j}$ is an integer for all $j \le k$.

Now consider:

$X_{k+1}=\left(x+\frac{1}{x}\right)^{k+1}$

if you examine the expansion you will find that pairs of terms can be grouped together to give integers by the induction hypothesis (with possibly an unpaired middle term which will be an integer on its own). Hence $X_{k+1}$ is an integer and the proof follows by strong induction.

CB
Thanks a lot!
I'll try that right away!