Results 1 to 5 of 5

Math Help - Combinatoric sequence, please help me

  1. #1
    Junior Member
    Joined
    Sep 2007
    Posts
    37

    Combinatoric sequence, please help me

    We have a integer sequence: a_{1}, a_{2}, a_{3}, .... and we have
    a_{1}=1
    a_{2}=2.
    a_{n}=3a_{n - 1}+5a_{n - 2}
    n=3,4,5....
    Does exist integer number x\geqslant 2 such that a_{x} is a divisor of a_{x + 1}a_{x + 2} ??
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Ununuquantium View Post
    We have a integer sequence: a_{1}, a_{2}, a_{3}, .... and we have
    a_{1}=1
    a_{2}=2.
    a_{n}=3a_{n - 1}+5a_{n - 2}
    n=3,4,5....
    Does exist integer number x\geqslant 2 such that a_{x} is a divisor of a_{x + 1}a_{x + 2} ??
    You can find the general expression for a_n.

    Define the generating function,
    f(x) = a_1+a_2x+a_3x^2+...
    Now consider,
    x^2f(x) - 3xf(x) -5x^2f(x) = 0
    And find the form of a_n ...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2007
    Posts
    37
    General expression doesn't work
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Ununuquantium View Post
    We have a integer sequence: a_{1}, a_{2}, a_{3}, .... and we have
    a_{1}=1
    a_{2}=2.
    a_{n}=3a_{n - 1}+5a_{n - 2}
    n=3,4,5....
    Does exist integer number x\geqslant 2 such that a_{x} is a divisor of a_{x + 1}a_{x + 2} ??
    Suppose (in order to get a contradiction) that a_n divides a_{n + 1}a_{n + 2}.

    Let p be a prime divisor of a_n. Then p must divide one or other of a_{n + 1} and a_{n + 2}. But this means that p divides two of the three terms in the relation a_{n+2}=3a_{n + 1}+5a_{n} and therefore it divides the third one as well. However, a_{n+1}=3a_{n}+5a_{n - 1}, and since p divides a_{n + 1} and a_{n} it must also divide a_{n-1}. Continuing in this way by "reverse induction", you see that p must divide a_{n-2}, a_{n-3}, ..., and eventually that p divides a_{1}=1.

    That contradiction shows more than was asked for, namely that none of the prime divisors of a_{n} can divide a_{n+1} or a_{n+2}.

    Edit: That proof doesn't quite work. It's okay unless p = 3 or 5. But those two primes will require some other argument. I don't have time to think about that just now.

    Second edit: No real problem with p = 3 or 5. Suppose that p = 3. The recurrence relation a_{n}=3a_{n - 1}+5a_{n - 2} says that if a_n is a multiple of 3 then so is a_{n-2}. The "reverse induction" procedure then tells us that either a_2 or a_1 is a multiple of 3, which is a contradiction.

    In the same way, if p = 5 and a_n is a multiple of 5 then the recurrence relation shows that a_{n-1} is a multiple of 5. Continuing down the sequence to a_1, we again get a contradiction.
    Last edited by Opalg; September 2nd 2007 at 08:35 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2007
    Posts
    37
    Yes:
    I made it also by induction, it is similar:
    First I prove that every number from the sequence is not divisible by 5:

    INDUCTION BASE: I see that 5 doesn't divide a_{k}, where k=3.
    Induction step: I will prove for arbitrary k\geqslant 3(integer)
    that if a_{k} is not divisible by 5 therefore a_{k+1} is also not divisible by 5.

    I do similar with division by 3.

    And then, also proving by induction I say:

    Every three consecutive numbers in the sequence a_{k}=3a_{k - 1}+5a_{k - 2} ( k\geqslant ) are relatively prime [we also know now that every number from the sequence is not divisible by 5 and 3]:.
    INDUCTION BASE: Let k=3 - so a_{1}, a_{2}, a_{3} are relatively prime.
    Induction step: I will prove that if a_{k}=3a_{k - 1}+5a_{k - 2} therefore a_{k+1}=3a_{k}+5a_{k - 1}. So, we see that a_{k}, a_{k - 1} are reletively prime - so a_{k+1} is also relatively prime with a_{k}, a_{k - 1} - it is easy to deduce.

    Taht's why there does not exist such x\geqslant 2 (integer of course) that a_{x} is divisor of a_{x + 1}a_{x + 2}


    Can anybody check my proof, please - I am not a specialist
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Even vs. Odd in a combinatoric proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 2nd 2011, 02:48 AM
  2. Two combinatoric problems
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 21st 2010, 06:16 PM
  3. Need help with Combinatoric Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2010, 10:21 PM
  4. combinatoric thing
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 11th 2008, 01:48 AM
  5. combinatoric identity
    Posted in the Statistics Forum
    Replies: 1
    Last Post: February 17th 2007, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum