青蛙跳荷叶概率问题

问题提出

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

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

初探题面

题目很简洁。

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

记\(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} \Rightarrow a_{n-1}-c_{n-1}=b_{n-2}-c_{n-2}\) \(b_{n-} c_{n}=a_{n-1}-b_{n-1} \Rightarrow b_{n-} c_{n}=b_{n-2}-c_{n-2}+c_{n-1}-b_{n-1}\)

令\(t_{n}=b_{n}- c_{n}=-\left(b_{n-1}-c_{n-1}\right)+\left(b_{n-2}-c_{n-2}\right)\) \(t_{n}=-t_{n-1}+t_{n-2} \quad (t_{0}=0, t_{1}=1, t_{2}=-1)\)

设\(t_{n}+m t_{n-1}=n\left(t_{n-1}+m t_{n-2}\right)\)

\[\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= n==$

令\(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 ,d_{n}=()^{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)}\)

---

数列\(\left\{ y_n \right\}\)为：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} \left((-1)^{n}+1\right) \]

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) \]