青蛙跳荷叶概率问题

问题提出

现有$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,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在控制台中运行这个程序。

javascript

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=\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)}$

---

数列$\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)$$