On an assignment, I am asked to solve for exponential generating function of the number of permutations $\pi=\{\pi_1, \pi_2,...\pi_n\}$ such that $$\pi_1 > \pi_2 < \pi3 > ... \pi_n$$
I know that the generating function satisfies the recurrence $$2A_{n+1}=\sum_{k=0}^n \binom{n}{k}A_kA_{n-k}$$
Although I am unsure of how to come to this recurrence on my own. Once I reach this point, my approach is as follows $$\begin{align}&\mathrm{Let}\ A(x)=\sum_{n=0}^\infty A_{n}\frac{x^n}{n!}\Rightarrow\ A'(x)=\sum_{n=0}^\infty A_{n+1}\frac{x^n}{n!} \\&2A'(x)=2\sum_{n=0}^\infty A_{n+1}\frac{x^n}{n!}=\sum_{n=0}^\infty \left(\sum_{k=0}^n \binom{n}{k}A_kA_{n-k}\right)\frac{x^n}{n!}=\left(\sum_{n=0}^\infty A_{n}\frac{x^n}{n!}\right)^2=A^2(x)\end{align}$$
From this point, have the the differential equation
$$2A'=A^2,\ A(0)=1$$
However, based on some research I have been doing online, it seems that this differential equation is incorrect and it should be
$$2A'=A^2+1,\ A(0)=1\Rightarrow\ A(x)=\sec\left(x\right)+\tan\left(x\right)$$
Could you please explain where the missing 1 comes from, and also how I would go about finding the recurrence from the initial sequence?
Thank you!
Your recurrence almost works, but it fails with $n=0$. There the left side is $2$ and the right side is $1$. So you need to add $1$ to $A(x)^2$ to make it work. The thing you are counting with $2A_{n+1}$ is the number of permutations of $[n+1]$ which are either "up-down" or "down-up". That is usually $2A_{n+1}$ but when $n=0$ the unique permutation of $[1]$ is both up-down and down-up, so the recurrence fails there.