求由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的且含有 $1$、$6$ 相邻的 $n$ 位数的个数．
【难度】
【出处】
2015年全国高中数学联赛河南省预赛
【标注】
【答案】
$6^n \cdot \left [ \dfrac{\sqrt{41} - 123}{246} \left(\dfrac{15+ 3\sqrt{41}}{36} \right)^{n-1} - \dfrac{\sqrt{41} - 123}{246} \left(\dfrac{15- 3\sqrt{41}}{36} \right)^{n-1} + 1\right]$
【解析】
设由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的且含有 $1$、$6$ 相邻的 $n$ 位数有 $a_{n}$ 个；记由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的首位数字是 $1$ 且含有 $1$、$6$ 相邻的 $n$ 位数有 $b_{n}$ 个．在每一个 $b_{n}$ 中交换 $1$ 和 $6$ 的位置由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的首位数字是 $6$ 且含有 $1$ 和 $6$ 相邻的 $n$ 位数也有 $b_{n}$ 个．
由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的且含有 $1$、$6$ 相邻的 $n$ 位数可以分三类：
第一类： 由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的首位数字是 $1$ 且含有 $1$、$6$ 相邻的 $n$ 位数，这样的数有 $b_{n}$ 个；
第二类： 由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的首位数字是 $6$ 且含有 $1$、$6$ 相邻的 $n$ 位数，这样的数有 $b_{n}$ 个；
第三类： 由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的首位数字是 $2$、$3$、$4$、$5$ 之一的且含有 $1$、$6$ 相邻的 $n$ 位数，这样的数的后 $n-1$ 位仍是由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的且含有 $1$、$6$ 相邻的 $n-1$ 位数共有 $4a_{n-1}$ 个，于是$$a_{n} = 2b_{n} + 4a_{n-1}.\qquad \text{ ① }$$而记由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的首位数字是 $1$ 且含有 $1$、$6$ 相邻的 $n$ 位数也可以分三类：
第一类： 第二位是 $6$ 的且含有 $1$、$6$ 相邻的 $n$ 位数，这些数的后 $n-2$ 位上的数字可以是 $1$、$2$、$3$、$4$、$5$、$6$ 任一，故共有 $6^{n-2}$ 个；
第二类： 第二位仍是 $1$ 的且含有 $1$、$6$ 相邻的 $n$ 位数，这些数的第二位起的后 $n-2$ 位上的数字是由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的首位数字是 $1$，且含有 $1$、$6$ 相邻的 $n-1$ 位数，有 $b_{n-1}$ 个；
第三类： 第二位是 $2$、$3$、$4$、$5$ 之一的且含有 $1$、$6$ 相邻的 $n$ 位数，这些数的后 $n-2$ 位上的数字是由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的且含有 $1$、$6$ 相邻的数，共有 $4a_{n-2}$ 个，于是$$b_{n} = 6^{n-2} +b_{n-1} + 4a_{n-2}.\qquad \text{ ② }$$由 ①、② 得 $a_{n} = 5a_{n-1} + 4a_{n-2} + 2\cdot 6^{n-2}$，且 $a_{1}=0,a_{2}=2$，
所以，$\dfrac{a_{n}}{6^n} = \dfrac{5}{6} \cdot \dfrac{a_{n-1}}{6^{n-1}} + \dfrac{1}{9} \cdot \dfrac{a_{n-2}}{6^{n-2}} + \dfrac{1}{18}.$
令 $c_{n} = \dfrac{a_{n}}{6^n}$，则 $c_{n} = \dfrac{5}{6} \cdot c_{n-1} + \dfrac{1}{9} \cdot c_{n-2} +\dfrac{1}{18}$，$c_{1}=0$，$c_{2} = \dfrac{1}{18}.$
进而 $c_{n} - 1 = \dfrac{5}{6} (c_{n-1} - 1) + \dfrac{1}{9}(c_{n-2} - 1)$，再令 $d_{n} = c_{n} - 1$，于是$$d_{n} = \dfrac{5}{6} d_{n-1} +\dfrac{1}{9}d_{n-2},d_{1} = -1,d_{2}=-\dfrac{7}{18}.$$故$$d_{n} = \dfrac{\sqrt{41} - 123}{246} \left(\dfrac{15+ 3\sqrt{41}}{36} \right)^{n-1} - \dfrac{\sqrt{41} - 123}{246} \left(\dfrac{15- 3\sqrt{41}}{36} \right)^{n-1} .$$于是$$a_{n} = 6^n \cdot \left [ \dfrac{\sqrt{41} - 123}{246} \left(\dfrac{15+ 3\sqrt{41}}{36} \right)^{n-1} - \dfrac{\sqrt{41} - 123}{246} \left(\dfrac{15- 3\sqrt{41}}{36} \right)^{n-1} + 1\right].$$
由数字 $1$、$2$、$3$、$4$、$5$、$6$ 构成的且含有 $1$、$6$ 相邻的 $n$ 位数可以分三类：
所以，$\dfrac{a_{n}}{6^n} = \dfrac{5}{6} \cdot \dfrac{a_{n-1}}{6^{n-1}} + \dfrac{1}{9} \cdot \dfrac{a_{n-2}}{6^{n-2}} + \dfrac{1}{18}.$
令 $c_{n} = \dfrac{a_{n}}{6^n}$，则 $c_{n} = \dfrac{5}{6} \cdot c_{n-1} + \dfrac{1}{9} \cdot c_{n-2} +\dfrac{1}{18}$，$c_{1}=0$，$c_{2} = \dfrac{1}{18}.$
进而 $c_{n} - 1 = \dfrac{5}{6} (c_{n-1} - 1) + \dfrac{1}{9}(c_{n-2} - 1)$，再令 $d_{n} = c_{n} - 1$，于是$$d_{n} = \dfrac{5}{6} d_{n-1} +\dfrac{1}{9}d_{n-2},d_{1} = -1,d_{2}=-\dfrac{7}{18}.$$故$$d_{n} = \dfrac{\sqrt{41} - 123}{246} \left(\dfrac{15+ 3\sqrt{41}}{36} \right)^{n-1} - \dfrac{\sqrt{41} - 123}{246} \left(\dfrac{15- 3\sqrt{41}}{36} \right)^{n-1} .$$于是$$a_{n} = 6^n \cdot \left [ \dfrac{\sqrt{41} - 123}{246} \left(\dfrac{15+ 3\sqrt{41}}{36} \right)^{n-1} - \dfrac{\sqrt{41} - 123}{246} \left(\dfrac{15- 3\sqrt{41}}{36} \right)^{n-1} + 1\right].$$
答案
解析
备注
