【教學】好題分享：如何以遞迴關係式解機率問題？

最近高中課堂上進行到了第二冊第1章，數列與級數。

這一段內容與國中數學第四冊有不少重疊，
主要多了「等比級數」、「遞迴關係式」、「數學歸納法」以及一些級數和公式。

這一篇文章，與同學們分享一道串連「遞迴關係式」、「費氏數列」的機率問題。

將一枚公正硬幣連擲ｎ次，在投擲過程中接連出現兩次正面向上的機率為多少？

記得我第一次看到這道題，是只有將硬幣連擲10次，但慢慢列舉也是很麻煩的，
還是要看出投擲次數之間的關係才行。

設此機率為 $Q_n$

先從次數較少的情況開始

連擲兩次，那麼必定為「正正」，機率為 $Q_2 = (\frac{1}{2})^2 = \frac{1}{4}$
連擲三次，那麼情況為「正正正、正正反、反正正」三種，機率為 $Q_3=3\times (\frac{1}{2})^3 = \frac{3}{8}$
連擲四次，情況為「正正正正、正正正反、正正反正、正反正正、反正正正、正正反反、反正正反、反反正正」 $Q_4=8\times (\frac{1}{2})^4 = \frac{1}{2}$

這樣一直列下去顯然不是個好辦法，我們必須觀察第 $n$ 次與前幾次連續出現兩正面機率的關係。

已知 $Q_1=0, Q_2=\frac{1}{4}$ 若 $n>2$ 時，可將其分成三個情況：

情況一：第一次正面，第二次為正面，則此機率為 $\frac{1}{4}$ ；
情況二：第一次正面，第二次為反面，則此機率為 $(\frac{1}{2})^2\times Q_{n-2}$
情況三：第一次反面，則此機率為 $\frac{1}{2}\times Q_{n-1}$

綜合以上3種情況，可得 $Q_n=\frac{1}{4}+\frac{1}{4}Q_{n-2}+\frac{1}{2}Q_{n-1}\tag{1}$

如何解以上的遞迴關係式(1)？

首先可以將這個遞迴關係式改寫為 $1-Q_n=\frac{1}{2}(1-Q_{n-1})+\frac{1}{4}(1-Q_{n-2})\tag{*}$

令 $P_n=1-Q_n$ ，則可將上式(*)寫成 $P_n=\frac{1}{2}P_{n-1}+\frac{1}{4}P_{n-2}\tag{2}$ 其中 $P_1=1, P_2=\frac{3}{4}$ 接著將第(2)式等號兩邊同乘以 $2^n$ 可得 $2^nP_n=2^{n-1}P_{n-1}+2^{n-2}P_{n-2}\tag{3}$ 為了方便起見，再來簡化一下符號，令 $S_n=2^nP_n$ ，

則第(3)式可改寫為 $S_n=S_{n-1}+S_{n-2} , n\geq 3$ 其中 $S_1=2, S_2=3$

有沒有覺得很眼熟，是不是很像費氏數列 $F_n$ 呢？

將兩者並列比較一下：
$\begin{aligned} S_n: 2, 3, 5, 8, 13, 21, 34, … \\ F_n: 1, 1, 2, 3, 5, 8, 13, … \end{aligned}$ 也就是說 $Q_n=F_{n+2}$ 且 $S_n=1-P_n=1-\frac{S_n}{2^n}$ 因此 $Q_n=1-P_n=1-\frac{S_n}{2^n}$
如果投擲十次，則 $Q_{10}=1-P_{10}=1-\frac{S_{10}}{2^{10}}=1-\frac{144}{1024}=\frac{55}{64}$

這篇文章就先寫到這邊，歡迎參考，若有謬誤，尚請不吝指正。