need to check strong induction proof

**issacnewton** · October 3rd 2011, 11:02 PM

Hi

here's problem i am trying to solve.

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

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

I have to prove this using strong induction. Let

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

so I have to prove that

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

strong induction means I have to prove

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

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

now let n=2 .

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

expanding the bracket , we have

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

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

so now consider n from 3 onwards. now

$n-1 < n$

since n is now taken from 3 onwards,

$1\leqslant n-1 < n$

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

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

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

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

$\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 ,

$1\leqslant n-2 < n$

from inductive hypothesis it follows that

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

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

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

$\therefore P(n)$

since n is arbitrary

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

is the reasoning right ??

**emakarov** · October 4th 2011, 02:38 AM

Yes, that's right. I would only say, "Since $\mathbb{Z}$ is closed under subtraction..." since you deduce $\left(x^n+\frac{1}{x^n}\right)\in \mathbb{Z}$ from $\left(x^n+\frac{1}{x^n}+x^{n-2}+\frac{1}{x^{n-2}}\right)\in \mathbb{Z}$ and $\left(x^{n-2}+\frac{1}{x^{n-2}}\right)\in \mathbb{Z}$ .

Thread: need to check strong induction proof

LinkBack

Thread Tools

Display

need to check strong induction proof

Re: need to check strong induction proof

Similar Math Help Forum Discussions

proof by strong induction

Strong Induction proof

Proof by strong induction?

Proof Using Strong Induction

Strong Induction proof