Results 1 to 2 of 2

Math Help - need to check strong induction proof

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

    need to check strong induction proof

    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 ??
    Last edited by issacnewton; October 4th 2011 at 12:35 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: need to check strong induction proof

    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}.
    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: November 27th 2011, 05:06 PM
  2. Strong Induction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 24th 2010, 11:01 AM
  3. Proof by strong induction?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2009, 08:51 AM
  4. Proof Using Strong Induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 27th 2009, 07:30 AM
  5. Strong Induction proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2008, 01:42 PM

/mathhelpforum @mathhelpforum