# Recurrence representation(s): $a(n+1)=a(n)(n-1/2)+o(1/n)$ and $a(n+1)=a(n)(n-1/2+o(1/n))$

I know that the recurrence $\displaystyle a(n+1)=a(n)(n-1/2)$ can be represented like $\displaystyle \frac{(2n-1)!!}{2^n}$

Actually the initial recurrence is slightly different: $$\displaystyle a(n+1)=a(n)(n-1/2)+o(1/n)$$

I am looking for the new representation of it in terms of $\displaystyle \frac{(2n-1)!!}{2^n}$.

Probably the question has to be refined. The recurrence is very close to the property of Kendall-Mann numbers http://oeis.org/A181609 that is why I am trying to find an interval of $\displaystyle n$'s when the $\displaystyle \frac{(2n-1)!!}{2^n}$ or similar representation works fine.

I understand that $\displaystyle o(1/n)$ is quite big error for the representation.

I am also interested in the case the recurrence is

$$\displaystyle a(n+1)=a(n)(n-1/2+o(1/n))$$

which is closer to the recurrence satisfied by the Kendall-Mann numbers.

• Clearly it makes a big difference whether you mean $a(n)(n-1/2+o(1/n))$ or $a(n)(n-1/2)+o(1/n)$. In the OEIS entry for the Kendall-Mann numbers you linked to, it is the former; do you actually mean the latter? – mjqxxxx Feb 24 '11 at 23:04
• Fire and forget? mjq asked a valid question... – Aryabhata Feb 26 '11 at 19:58
• Sorry Moron and mjqxxxx, I was too invloved with "Bath towel on the rope" question. The actual recurrence to study futher: $M(n+1)/M(n)=n-1/2+o(1/n)$ from OEIS. – Mikhail G Feb 27 '11 at 19:48
• I'm not sure I understand the connection with the Kendall-Mann numbers. The K-M numbers at oeis.org/A000140 have a combinatorial interpretation but no closed form function or even a recurrence. The numbers defined at oeis.org/A181609, despite the title, just seem to be equal to K-M for the first few then start to diverge. How is A181609 associated with K-M? – Mitch Mar 4 '11 at 23:05

For the recurrence $\displaystyle a_{n+1} = (n - 1/2) a_n + o(1/n)$

If you set $\displaystyle a_n = \frac{(2n-1)!!}{2^n} - e_n$,

you get $\displaystyle e_{n+1} - e_n = o\left(\frac{1}{n}\right)$ and thus $e_n = o(\log n)$.

Using Stirling's approximation, I believe we have that

$\displaystyle \frac{(2n-1)!!}{2^n} \approx \frac{Kn!}{\sqrt{n}}$

Thus we get

$$\lim_{n \to \infty} \frac{2^n a_n}{(2n-1)!!} = 1$$

Now if the recurrence was $\displaystyle a_{n+1} = a_{n} (n - 1/2 + o(1/n))$

Set $\displaystyle a_{n+1} = e_n\frac{(2n-1)!!}{2^n}$

We get

$\displaystyle \frac{e_{n+1}}{e_n} = 1 + o(1/n^2)$

And thus

$\displaystyle e_n = e_1 \prod_{k=1}^{n-1} (1 + o(1/k^2))$

Now using $1 + x \le e^x$ we get that

$\displaystyle e_n = \mathcal{O}(1)$

and we can easily show that $\displaystyle e_n$ is convergent.

Thus

$$a_n \sim \frac{C(2n-1)!!}{2^n}$$

for some constant $\displaystyle C = \lim_{n \to \infty} e_n$ .

We could chose your $\displaystyle f(n) = o(1/n)$ as we like, to make this constant different from $\displaystyle 1$.

• @MIke: Just edited! – Aryabhata Feb 24 '11 at 20:30
• I'm not surprised you caught that yourself. :) – Mike Spivey Feb 24 '11 at 20:30
• @MIke: ..... :-) – Aryabhata Feb 24 '11 at 20:31
• @Moron: Let us look closer at Kendall-Mann numbers oeis.org/A000140 For eg $n=19$ $3344822488498265$, $n=20$ $62119523114983224$. How could you apply your result for $a_{n}$? if the numbers are too small, well, let's take another ( for eg we can calculte it with Pati GP) – Mikhail G Feb 28 '11 at 17:51
• @Mikhail: I don't understand. All I claimed was that the ratio tends to a constant, which depends on the function which is $o(1/n)$. Note I have been assuming that $\frac{(2n-1)!!}{2^n}$ does indeed satisfy the recurrence you state and haven't tried to verify it. Are you saying you found a mistake? – Aryabhata Feb 28 '11 at 17:54