hihoCoder #1164 随机斐波那契

时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述

大家对斐波那契数列想必都很熟悉:

$a_0 = 1, a_1 = 1, a_i = a_{i-1} + a_{i-2}, (i > 1)$。

现在考虑如下生成的斐波那契数列:

$a_0 = 1, a_i = a_j + a_k, i > 0, j, k$从$[0, i-1]$的整数中随机选出（$j$和$k$独立）。

现在给定$n$，要求求出$E(a_n)$，即各种可能的$a$数列中$a_n$的期望值。
输入

一行一个整数$n$，表示第$n$项。($1 \le n \le 500$)
输出

一行一个实数，表示答案。你的输出和答案的绝对或者相对误差小于$10^{-6}$时被视为正确答案。
样例解释

共存在3种可能的数列

1,2,2  1/4

1,2,3  1/2

1,2,4  1/4

所以期望为3。

样例输入

2

样例输出

3.000000

分析：这道题要特别注意j和k独立这个条件，在这个条件下我们可以得到$E(a_n)$（以下简写成$E_n$）的一个表达式
$E_n = 2S_{n-1} / n$，                        (1)
其中$S_n$定义成
$S_n = E_0 +  E_1 + E_2 + \dots + E_n$
易见
$E_n = S_n - S_{n-1}$　　                     (2)
下面我将从上面的两个式子出发推出$E_n$关于$n$的表达式。
(1)式即
$nE_n = 2  S_{n-1}$　　　                 (3)
从而亦有
$(n+1) E_{n+1} = 2 S_n$　　             (4)
(4) - (3)得
$(n+1)  E_{n+1} - n  E_n = 2  E_n$
移项
$(n+1)  E_{n+1} = (n+2)  E_n$
亦即
$\dfrac{E_{n+1}} {E_n} = \dfrac{n+2} {n+1}$　　　　(5)
进而得到
$E_n = (n+1) E_0 = n+1$　　　　　　  (6)

P.S. hihoCoder上给的题解用归纳法证明了这个结论。