问题提出

现有m (m ≥ 3)片荷叶围成一圈，编号为A, B, C,⋯。初始时青蛙在荷叶A，每次可跳跃到相邻的2片荷叶上（比如，如果青蛙此时在B上，那么它下一次可以跳到A或C）。记青蛙跳n次后回到荷叶A上的概率为f(m, n)，求f(m, n)关于m, n (m, n ∈ ℕ)的通项。

提示：依题意，f(m, 0) = 1, f(m, 1) = 0, f(m, 2) = 0.5

初探题面

题目很简洁。

f(m, n)的分母为2ⁿ（不约分的情况下），因为跳n次总情况数为2ⁿ。

记f(m, n)的分子为a，即$f(m,n)=\dfrac{a}{2^n}$.

那么a是多少呢？我写了个程序，试探了几种情形。

代码中，变量 hy表示总的荷叶数(即题干中的m)，str输出从1到20的表格，str2输出f(m, n)的前几项。

你可以按下F12在控制台中运行这个程序。

hy=5;//手动修改m的值

var tArray = new Array();
tArray[0]=[null,1,0,0,0,0,0,0,0,0,0,0,0];//我们不需要t[x][0]
var str2="";
for(var k=1;k<18;k++){
    str="";
	tArray[k]=new Array();
	tArray[k][1]=tArray[k-1][2]+tArray[k-1][hy];
    str=k+":\t"+tArray[k][1]+"\t";
    str2=str2+tArray[k][1]+", ";
	tArray[k][hy]=tArray[k-1][hy-1]+tArray[k-1][1];
	for(var j=2;j<=hy-1;j++){
		tArray[k][j]=tArray[k-1][j+1]+tArray[k-1][j-1];
        str=str+tArray[k][j]+"\t";
 	}
    str=str+tArray[k][hy];
	console.log(str);
}
console.log(hy+"片荷叶：\n"+str2);

5片荷叶

m = 5的时候，记x_n = f(5, n). 则$x_n=\dfrac{a_n}{2^n}$

则有：

$$\left \{ \begin{array}{l} a_n=2b_{n-1}\\ b_n=a_{n-1}+c_{n-1}\\ c_n=c_{n-1}+b_{n-1}\\ a_n+2b_n+2c_n=2^n\end{array} \right. $$

a_n − c_n = b_n − 1 − c_n − 1 ⇒ a_n − 1 − c_n − 1 = b_n − 2 − c_n − 2 b_n−c_n = a_n − 1 − b_n − 1 ⇒ b_n−c_n = b_n − 2 − c_n − 2 + c_n − 1 − b_n − 1

令t_n = b_n − c_n = −(b_n − 1 − c_n − 1) + (b_n − 2 − c_n − 2) t_n = −t_n − 1 + t_n − 2 (t₀ = 0, t₁ = 1, t₂ = −1)

设t_n + mt_n − 1 = n(t_n − 1 + mt_n − 2)

$$\left\{\begin{array}{ccc}m n=1 & m(m-1)=1 \\ n-m=-1 & m^{2}-m-1=0\end{array}\right.$$

得$m=\dfrac{1+\sqrt{5}}{2} \quad n=\dfrac{2}{(1+\sqrt{5})}=\dfrac{\sqrt{5}-1}{2}$ 或$m=\dfrac{1-\sqrt{5}}{2} \quad n=\dfrac{2}{(1-\sqrt{5})}=\dfrac{\sqrt{5}+1}{-2}$

令$d_{n}=t_{n}+\dfrac{1+\sqrt{5}}{2} t_{n-1}$, 则$d_{n+1}=\dfrac{\sqrt{5}-1}{2} d_n$

$d_{1}=1 ,\quad d_{n}=\left(\dfrac{\sqrt{5}-1}{2}\right)^{n-1}$

$t_{n}+\dfrac{1+\sqrt{5}}{2} t_{n-1}=\left(\dfrac{\sqrt{5}-1}{2}\right)^{n-1}$

b_n − c_n = t_n$=\dfrac{\left(\sqrt{5}+3\right) 2^{1-n} \left(-\sqrt{5}-3\right)^{-n} \left(-\sqrt{5}-1\right)^n \left(\left(-\sqrt{5}-3\right)^n-2^n\right)}{\left(\sqrt{5}+1\right) \left(\sqrt{5}+5\right)}$

数列{y_n}为：0, 2, 0, 6, 2, 20, 14, 70, 72, 254, 330, 948, 1430, 3614, 6008, 13990, 24786, 54740, 101118, ...

根据Mathematica的 FindSequenceFunction函数拟合，可以得到：

$$ y_n=\dfrac{1}{5} \left(2 \left(\dfrac{\sqrt{5}}{2}-\dfrac{1}{2}\right)^{\text{n}}+2^{\text{n}}+2 \left(-\dfrac{\sqrt{5}}{2}-\dfrac{1}{2}\right)^{\text{n}}\right) $$

$\therefore f(5,n)=x_n=\dfrac{y_n}{2^n}$

3片荷叶

数列b_n为：0, 2, 2, 6, 10, 22, 42, 86, 170, 342, 682, 1366, 2730, 5462, 10922, 21846, 43690, ... 拟合得：$b_n=\dfrac{1}{3} \left(2 (-1)^{n}+2^{n}\right)$

可得$a_n= \dfrac{ 2 (-1)^{n}+2^{n}}{3 \times 2^n}$

同时根据数列递推式我们不难发现，$a_n=\dfrac{1}{2}(1-a_{n-1})$，由此可得通项。

7片荷叶

数列b_n为：0, 2, 0, 6, 0, 20, 2, 70, 18, 252, 110, 924, 572, 3434, 2730, 12902, 12376, 拟合失败。

4片荷叶

数列b_n为：0, 2, 0, 8, 0, 32, 0, 128, 0, 512, 0, 2048, 0, 8192, 0, 32768, 0, ... 拟合得：

b_n = 2^n − 2((−1)ⁿ + 1)

6片荷叶

数列b_n为：0, 2, 0, 6, 0, 22, 0, 86, 0, 342, 0, 1366, 0, 5462, 0, 21846, 0, ... 拟合得：

$$ b_n=\dfrac{1}{6} \left((-1)^{n}+1\right) \left(2^{n}+2\right) $$

8片荷叶

0, 2, 0, 6, 0, 20, 0, 72, 0, 272, 0, 1056, 0, 4160, 0, 16512, 0,.. 拟合得：

$$ b_n=\dfrac{1}{8} \left((-1)^{n}+1\right) \left(2^{\dfrac{n}{2}+1}+2^{n}\right) $$