# need to check strong induction proof

• Oct 3rd 2011, 11:02 PM
issacnewton
need to check strong induction proof
Hi

here's problem i am trying to solve.

Suppose that $\displaystyle x\neq 0$ is a real number and $\displaystyle x+1/x$ is an integer.
Prove that

$\displaystyle \forall n \geqslant 1 \;\; x^n+1/x^n \; \in \mathbb{Z}$

I have to prove this using strong induction. Let

$\displaystyle P(n)=[(n\geqslant 1)\Rightarrow ( x^n+1/x^n \; \in \mathbb{Z})]$

so I have to prove that

$\displaystyle \forall n\in \mathbb{N}\; P(n)$

strong induction means I have to prove

$\displaystyle \forall n[(\forall k < n P(k))\Rightarrow P(n)]$

so let n be arbitrary and suppose $\displaystyle \forall k < n P(k)$ and since i have to prove
P(n) , lets suppose $\displaystyle n \geqslant 1$. Even though this is proof by strong induction, i will
prove some base cases.
If n=1 then $\displaystyle x+1/x \; \in \mathbb{Z}$ by hypothesis

now let n=2 .

$\displaystyle \because x+1/x \; \in \mathbb{Z} \Rightarrow (x+1/x)^2 \in \mathbb{Z}$

expanding the bracket , we have

$\displaystyle x^2+1/x^2 + 2 \;\;\in \mathbb{Z}$

$\displaystyle \because 2 \in \mathbb{Z} \;\;\therefore (x^2+1/x^2) \; \in \mathbb{Z}$

so now consider n from 3 onwards. now

$\displaystyle n-1 < n$

since n is now taken from 3 onwards,

$\displaystyle 1\leqslant n-1 < n$

letting k=n-1 in the inductive hypothesis, we can deduce that

$\displaystyle \left(x^{n-1}+\frac{1}{x^{n-1}}\right) \; \in \mathbb{Z}$

$\displaystyle \because (x+1/x)\in \mathbb{Z} \quad \therefore (x+1/x)\left(x^{n-1}+\frac{1}{x^{n-1}}\right)\in \mathbb{Z}$

now expanding, we get

$\displaystyle \left(x^n+\frac{1}{x^n}+x^{n-2}+\frac{1}{x^{n-2}}\right)\in \mathbb{Z}$

now I will first prove that

$\displaystyle \left(x^{n-2}+\frac{1}{x^{n-2}}\right)\in \mathbb{Z}$

we know that n-2 < n and since n is going from 3 onwards ,

$\displaystyle 1\leqslant n-2 < n$

from inductive hypothesis it follows that

$\displaystyle \left(x^{n-2}+\frac{1}{x^{n-2}}\right)\in \mathbb{Z}$

and since $\displaystyle \;\mathbb{Z}\;$ is closed under addition , it follows that

$\displaystyle \left(x^n+\frac{1}{x^n}\right)\in \mathbb{Z}$

$\displaystyle \therefore P(n)$

since n is arbitrary

$\displaystyle \forall n\in \mathbb{N}\; P(n)\qquad\qquad \blacksquare$

is the reasoning right ??
• Oct 4th 2011, 02:38 AM
emakarov
Re: need to check strong induction proof
Yes, that's right. I would only say, "Since $\displaystyle \mathbb{Z}$ is closed under subtraction..." since you deduce $\displaystyle \left(x^n+\frac{1}{x^n}\right)\in \mathbb{Z}$ from $\displaystyle \left(x^n+\frac{1}{x^n}+x^{n-2}+\frac{1}{x^{n-2}}\right)\in \mathbb{Z}$ and $\displaystyle \left(x^{n-2}+\frac{1}{x^{n-2}}\right)\in \mathbb{Z}$.