Results 1 to 8 of 8

Math Help - recursive definitions

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    73

    recursive definitions

    For n>= 1 let a(sub n) be the number of ways in which 2n people can be paired to do n simulataneous projects. Find a recurrence relation for a(sub n)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    a_{n+1}=a_n+2n(2n-1)a_{n-1}
    and a_1=1,a_2=3
    is It right?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    773
    This reminds me the following anecdote about the physicist Paul Dirac, one of the founders of quantum mechanics.
    Dirac was working on an equation on the board. Turning around after to a silent audience he asked for any questions. A person in audience raised a hand and said "I do not understand such-and-such an equation". To which Dirac replies, "That's not a question, it's a statement."
    I do not mean to be rude in any way, but in addition to just the problem statement it would be nice to see some approaches you tried to solve the problem and the difficulties you encountered.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2009
    Posts
    73
    I dont think that recurrence relation works since a _ 2 = 3 but when u plug it into the reccurence to find a_2 it doesnt come out.

    Ive been working on it and cant seem to find anything that is working for me. I tried many combinations of 2n(n-1)a_(n-2) becauase I believe that part is correct Im just unsure of how to get the a_(n-1) term
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2009
    Posts
    73
    ooops typo 2n(2n-1)a_(n-2)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    773
    What about this reasoning? We want to find a_{n+1}. Suppose we have 2(n+1)=2n+2 people. Let's arbitrarily pick one of them. This person can be paired in 2n+1 ways. After this person is paired, we have 2n people left, and we already know in how many ways they can be paired. It seems that all pairings thus obtained are different and cover everything.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,616
    Thanks
    1579
    Awards
    1
    Quote Originally Posted by scubasteve123 View Post
    For n>= 1 let a(sub n) be the number of ways in which 2n people can be paired to do n simulataneous projects. Find a recurrence relation for a(sub n)
    Take note, putting 2n people into groups of two each can be done in \frac{(2n)!}{2^n(n!)} ways.
    These are unordered partitions.

    Thus it is not hard to find the recursion.
    a_1=1 and a_{n+1}=(2n+1)\cdot a_n.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    It is very easy to see that two different recursive definition:
    <br />
a_{n+1}=a_n+2n(2n-1)\cdot a_{n-1} \text { where }a_1=1,a_2=3;

    a_{n+1}=(2n+1)\cdot a_n \text{ where }a_1=1
    Define the same number sequence!
    But the question is :
    Without using Mathematical Induction, how to get another recursive definition If one of the recursive definition is known?
    How to solve the first recursive relation without using the Mathematics Induction?
    can anybody give a solution or hint?
    Last edited by Shanks; November 26th 2009 at 06:27 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set Recursive Definitions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 12th 2011, 03:46 AM
  2. definitions
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: March 21st 2010, 11:02 AM
  3. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 29th 2009, 07:32 AM
  4. recursive definitions
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: August 1st 2007, 10:50 PM
  5. definitions
    Posted in the Algebra Forum
    Replies: 3
    Last Post: February 21st 2007, 08:34 PM

Search Tags


/mathhelpforum @mathhelpforum