3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ – mjqxxxx Feb 24 '11 at 23:04
  • $\begingroup$ Fire and forget? mjq asked a valid question... $\endgroup$ – Aryabhata Feb 26 '11 at 19:58
  • $\begingroup$ 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. $\endgroup$ – Mikhail G Feb 27 '11 at 19:48
  • $\begingroup$ 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? $\endgroup$ – Mitch Mar 4 '11 at 23:05
2
$\begingroup$

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$.

$\endgroup$
13
  • $\begingroup$ @MIke: Just edited! $\endgroup$ – Aryabhata Feb 24 '11 at 20:30
  • $\begingroup$ I'm not surprised you caught that yourself. :) $\endgroup$ – Mike Spivey Feb 24 '11 at 20:30
  • $\begingroup$ @MIke: ..... :-) $\endgroup$ – Aryabhata Feb 24 '11 at 20:31
  • $\begingroup$ @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) $\endgroup$ – Mikhail G Feb 28 '11 at 17:51
  • $\begingroup$ @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? $\endgroup$ – Aryabhata Feb 28 '11 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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