$a_1=1, a_2=1, a_3=3, a_4=15, a_5=105$

Reccurence formula is

$a_{k+1}=\sum\limits_{\lambda_1+\lambda_2+\ldots+\lambda_s=k,\ \lambda_i\geq1} a_{\lambda_1}a_{\lambda_2}...a_{\lambda_s}{k \choose \lambda_1\lambda_2...\lambda_s}$ (1)

($\lambda_1,\lambda_2,\ldots,\lambda_s$ are not ordered)

I need to prove that $a_k=(2k-3)!!$

I've represented (1) into this form

$a_{k+1}\frac{t^k}{k!}=\sum\limits_{\lambda_1+\lambda_2+\ldots+\lambda_s=k,\ \lambda_i\geq1} \prod \limits_{i=1} a_{\lambda_i} \frac{t^{\lambda_i}}{\lambda_i!}$ (2)

I think that after summing by k left side of (2) gives $A'(t)$, where $A(t)=\sum a_i \frac{t^i}{i!}$ (exponential generating function)

but what will be the rightt side of (2)?

is it good to use exponential g.f. here?


closed as off-topic by Noah Stein, Vladimir Dotsenko, Stefan Kohl, Ryan Budney, user9072 Apr 1 '14 at 16:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Noah Stein, Vladimir Dotsenko, Ryan Budney
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Have you checked OEIS? $\endgroup$ – Per Alexandersson Mar 22 '14 at 16:59
  • $\begingroup$ yes, there is written that $A=1-\sqrt{1-2t}$ $\endgroup$ – Radmir Mar 23 '14 at 13:16

right side of (2) is $1+A(t)+A^2(t)+\ldots$

so we get $A'(t)=\frac{1}{1-A(t)} \\ A'(1-A)=1 \Rightarrow A'-AA'=1 \Rightarrow A-\frac{1}{2}A^2=t+C$

obviously, $C=0$, so we get quadratic equation

$A^2-2A+2t=0 \\ A(t)=1-\sqrt{1-2t}=\sum{\dbinom{\frac{1}{2}}{k}(-2)^kt^k}=\sum{(2k-3)!!\frac{t^k}{k!}} $

finally $a_k=(2k-3)!!$


Not the answer you're looking for? Browse other questions tagged or ask your own question.