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, $\displaystyle x \neq 0$ and $\displaystyle x+1/x$ is an integer. Prove by strong induction that for all n ≥ 1, $\displaystyle 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, $\displaystyle x \neq 0$ and $\displaystyle x+1/x$ is an integer. Prove by strong induction that for all n ≥ 1, $\displaystyle x^n +1/x^n$ is an integer.

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

Now consider:

$\displaystyle 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:

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

Hence as $\displaystyle X_{k+1}$ is an integer as are all the other terms by the induction hypothesis so is [mATH]u_{k+1}[/tex] and so the proof follows by strong induction.

CB

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

Now consider:

$\displaystyle 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 $\displaystyle X_{k+1}$ is an integer and the proof follows by strong induction.

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