# recursive definitions

• Nov 23rd 2009, 09:31 PM
scubasteve123
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)
• Nov 24th 2009, 01:43 AM
Shanks
$\displaystyle a_{n+1}=a_n+2n(2n-1)a_{n-1}$
and $\displaystyle a_1=1,a_2=3$
is It right?
• Nov 24th 2009, 02:01 AM
emakarov
This reminds me the following anecdote about the physicist Paul Dirac, one of the founders of quantum mechanics.
Quote:

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.
• Nov 24th 2009, 04:49 PM
scubasteve123
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
• Nov 24th 2009, 04:51 PM
scubasteve123
ooops typo 2n(2n-1)a_(n-2)
• Nov 25th 2009, 02:53 AM
emakarov
What about this reasoning? We want to find $\displaystyle a_{n+1}$. Suppose we have $\displaystyle 2(n+1)=2n+2$ people. Let's arbitrarily pick one of them. This person can be paired in $\displaystyle 2n+1$ ways. After this person is paired, we have $\displaystyle 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.
• Nov 25th 2009, 06:27 AM
Plato
Quote:

Originally Posted by scubasteve123
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 $\displaystyle 2n$ people into groups of two each can be done in $\displaystyle \frac{(2n)!}{2^n(n!)}$ ways.
These are unordered partitions.

Thus it is not hard to find the recursion.
$\displaystyle a_1=1$ and $\displaystyle a_{n+1}=(2n+1)\cdot a_n$.
• Nov 25th 2009, 05:57 PM
Shanks
It is very easy to see that two different recursive definition:
$\displaystyle a_{n+1}=a_n+2n(2n-1)\cdot a_{n-1} \text { where }a_1=1,a_2=3$;

$\displaystyle 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?