每日一题[2164]跳跃的青蛙

已知池塘中有按顺序编号为 $1,2,3,\cdots$ 的一列荷叶，一只青蛙从 $1$ 号荷叶出发进行跳跃．当青蛙位于 $k$ 号荷叶时，等可能的跳到 $k+1$ 或 $k+2$ 号荷叶．设青蛙在行经过程中会落在 $7$ 号荷叶的概率的最间分数表示为 $\dfrac pq$，则 $p+q=$_______．

答案    $096$．

解析    设 $p_n$ 为青蛙会落在 $n$ 号荷叶的概率，则 $p_1=1$，$p_2=\dfrac 12$，且当 $n\geqslant 3$ 时，有 $$p_n=\dfrac 12p_{n-1}+\dfrac 12p_{n-2},$$ 从而 $$\begin{array}{c|ccccccc}\hline n&1&2&3&4&5&6&7\\ \hline p_n&1&\dfrac 12&\dfrac 34&\dfrac 58&\dfrac{11}{16}&\dfrac{21}{32}&\dfrac{43}{64}\\ \hline\end{array}$$ 因此 $p+q=43+64=107$． 事实上，有 $a_n=\dfrac 23\left(1-\left(-\dfrac 12\right)^n\right)$（$n\in\mathbb N^{\ast}$）．