某動漫中的一道數列題

03-04

數列 $left{ p_{n} ight}$ 按如下方式定義：

$p_{1}=1$ ， $p_{2}=1$ ， $p_{n+2}=p_{n+1}+p_{n}$ （ $ngeq1$ ），這個數列叫做Fibonacci數列，它的通項公式為：

$p_{n}=frac{1}{sqrt{5}}left[ left( frac{1+sqrt{5}}{2} ight)^{n}-left( frac{1-sqrt{5}}{2} ight)^{n} ight]$ （ $nin N^{*}$ ）

根據以上信息回答下列問題：

將一個自然數列 $left{ x_{n} ight}$ （ $nin N^{*}$ ）按如下規則定義：其中每一個數都是由數字 $0$ 或 $1$ 組成，並且滿足

(A) $x_{1}=1$ ；

(B) $x_{n+1}$ 為自然數，是將 $x_{n}$ 中的數字 $0$ 替換成 $1$ ，數字 $1$ 替換成 $10$ 而得到.

例如： $x_{1}=1$ , $x_{2}=10$ , $x_{3}=101$ , $x_{4}=10110$ , $x_{5}＝10110101$ ,…

求解：

(1) $a_{n}$ ，它被定義為 $x_{n}$ 中的數字個數；

(2) $b_{n}$ ，它被定義為 $x_{n}$ 中的「01」的出現次數.

例如： $b_{1}=0$ , $b_{2}=0$ , $b_{3}=1$ , $b_{4}=1$ , $b_{5}=3$

解：

(1)

令數列 $left{ x_{n} ight}$ 中的 $0$ 的個數為 $c_{n}$ ，1的個數為 $d_{n}$

顯然

$a_{n}=c_{n}+d_{n}$

$c_{n+1}=d_{n}$

$d_{n+1}=c_{n}+d_{n}$

$a_{n+1}=c_{n+1}+d_{n+1}=c_{n}+2d_{n}$

$c_{n+2}=d_{n+1}=c_{n}+d_{n}$

$d_{n+2}=c_{n+1}+d_{n+1}=c_{n}+2d_{n}$

$a_{n+2}=c_{n+2}+d_{n+2}=2c_{n}+3d_{n}$

顯然有

$c_{n+2}=c_{n+1}+c_{n}$ $d_{n+2}=d_{n+1}+d_{n}$ $a_{n+2}=a_{n+1}+a_{n}$

（ $nin N^{*}$ ）

注意到 $a_{1}=1$ ， $a_{2}=2$

顯然

$a_{n}=p_{n+1}=frac{1}{sqrt{5}}left[ left( frac{1+sqrt{5}}{2} ight)^{n+1}-left( frac{1-sqrt{5}}{2} ight)^{n+1} ight]$ （ $nin N^{*}$ ）

(2)

由題顯然可得， $b_{n+1}$ 等於 $x_{n}$ 中不處於最末一位的 $1$ 的個數

且對於數列 $left{ x_{n} ight}$ ，顯然其奇數項末位為 $1$ ，偶數項末位為 $0$

則

$b_{2n}=d_{2n-1}-1$

$b_{2n+1}=d_{2n}$

注意

$d_{n+2}=d_{n+1}+d_{n}$

（ $nin N^{*}$ ）

$d_{1}=1$ ， $d_{2}=1$

則

$d_{n}=p_{n}=frac{1}{sqrt{5}}left[ left( frac{1+sqrt{5}}{2} ight)^{n}-left( frac{1-sqrt{5}}{2} ight)^{n} ight]$

（ $nin N^{*}$ ）

$b_{2n}=d_{2n-1}-1=p_{2n-1}-1$

$b_{2n+1}=d_{2n}=p_{2n}$

$b_{2n}=frac{1}{sqrt{5}}left[ left( frac{1+sqrt{5}}{2} ight)^{2n-1}-left( frac{1-sqrt{5}}{2} ight)^{2n-1} ight]-1$

$b_{2n+1}=frac{1}{sqrt{5}}left[ left( frac{1+sqrt{5}}{2} ight)^{2n}-left( frac{1-sqrt{5}}{2} ight)^{2n} ight]$

（ $nin N^{*}$ ）

綜上

$b_{n}=frac{1}{sqrt{5}}left[ left( frac{1+sqrt{5}}{2} ight)^{n-1}-left( frac{1-sqrt{5}}{2} ight)^{n-1} ight]-frac{1}{2}left[ 1+left( -1 ight)^{n} ight]$

（ $nin N^{*}$ ）

關於Fibonacci數列通項公式的推導，見：

知乎用戶：斐波那契數列通項公式是怎樣推導出來的？