递推数列的通项表达或变化趋势
第$1$轮同时抛$n$枚硬币，以后每$1$轮都是将正面朝上的硬币捡起来重抛，
直到所有的硬币都反面朝上为止。
问：所抛轮数的期望值是多少？
猜想：$F(n)$ ~ $O(\log_2 n)$ 本帖最后由 云梦 于 2013-9-18 09:26 编辑
从趋势来看确实F(n)与Log(n)有关，但不是Log(2n),比2n要大.介于n<n2之间。
n=3000时,F(n)~1.609Log
首先容易得到$F_n\leq \frac{2^n}{2^n-1}(1+max_{k<n}F_k)$，因此粗略估计$F_n=O(n)$，是个缓慢变化的函数，而求和式中的$C_n^k$是个在$k=n/2$处有极为尖锐的单峰的函数，因此整个求和式的值主要由$k$~$n/2$附近的求和决定，由于$F_n$是$n$的缓变函数，在这个求和范围内可以看成常数，这部分求和可以很方便地化为高斯积分，从而得到近似关系$F_n=1+F_{n/2}$，$F_n$~$log_2 n$。由于求和毕竟不同于积分，进一步的考察没有太大意义。事实上$F_n$~$\log_2 n+c+d_i/i$，$c$约等于$1.332746$，$d_i=g(sqrt(i))$是一个振荡函数（或者是振荡函数加一个缓变函数），这里离散性的影响已经明显地表现出来了。
页:
[1]