Results 1 to 2 of 2

Thread: need to check strong induction proof

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    208

    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 ??
    Last edited by issacnewton; Oct 3rd 2011 at 11:35 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    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}$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by strong induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Nov 27th 2011, 04:06 PM
  2. Strong Induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 24th 2010, 10:01 AM
  3. Proof by strong induction?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 5th 2009, 07:51 AM
  4. Proof Using Strong Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jul 27th 2009, 06:30 AM
  5. Strong Induction proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 5th 2008, 12:42 PM

/mathhelpforum @mathhelpforum