Results 1 to 2 of 2

Math Help - some problem in strong induction

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

    some problem in strong induction

    hi

    here is a problem i am trying to do.

    \forall m,n \in \mathbb{N}[(m\lvert n)\Rightarrow (F_m\lvert F_n)]

    where F_n is nth Fibonacci number. following is my attempt to prove.

    let

    P(n)=[(m\lvert n) \Rightarrow (F_m\lvert F_n)]

    let m be arbitrary in N. so the goal is

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

    where k runs in N.so let n be arbitrary in N. suppose

    \forall k< n P(k) and

    since we have to prove P(n), suppose

    m\lvert n

    I have proven some base cases for n=0,1,2 so the next case is
    n\geqslant 3

    now

    1\leqslant n-2 < n\quad \therefore (n-2)\in \mathbb{N}

    so using inductive hypothesis, it follows that

    m\lvert (n-2)\Rightarrow F_m\lvert F_{n-2}

    we can also come up the following conclusion for n-1,

    m\lvert (n-1)\Rightarrow F_m\lvert F_{n-1}

    but I don't know what to do with this. I thought of another approach. since I assumed that

    m\lvert n\quad \therefore \exists k\in \mathbb{Z} (mk=n)

    \therefore mk=n \quad \because m,n\in \mathbb{N}\Rightarrow k\in\mathbb{N}

    \therefore m(k-1)+m=n\quad \therefore m(k-1)=n-m

    \therefore m\lvert (n-m)

    I can use this for the inductive hypothesis , but I can't be sure if

    (n-m)<n

    because since m is arbitrary in N,m could be zero, in which case the above inequality fails.

    So what approach should I take here ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    198

    Re: some problem in strong induction

    I learned through some other forums that we have to have the condition

    m>0\quad n>0

    after that the proof is easy
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] strong induction problem involving power set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 8th 2011, 01:32 AM
  2. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  3. Strong Induction Problem using Summations
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 3rd 2009, 09:12 AM
  4. Strong Induction help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 7th 2009, 08:48 PM
  5. Strong Induction Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2008, 05:09 AM

/mathhelpforum @mathhelpforum