問題#Ⅰ013 ★★☆☆
整数を項とする数列$\{x_n\}$を、$x_1=2$、$x_2=8$ と関係
$x_{n+2}=2(x_{n+1}+x_n)$ $(n=1,2,3,\cdots)$
で定めるとき、次の問に答えよ。
（１）$x_n$を$3$で割ったときの余りを求めよ。
（２）$x_n$を$n$の式で表せ。
（３）$n$を正の整数とするとき、$(1+\sqrt{3})^n$を越えない最大の整数を$3$で割ったときの余りを求めよ。
《ポイント》
（１）は小さい$n$について$x_n$を$3$で割ったときの余りを調べることで方針が見えるはずです。（２）は$3$項間漸化式の一般項の導出であり、ここまでの誘導設問ができていれば（３）はほとんどオマケ問題です。
《解答例》
（１）
$x_n$を$3$で割ったときの余りがすべての正の整数$n$について$2$であることを数学的帰納法により示す。
$x_1=2$、$x_2=8$ より、$x_1$、$x_2$を$3$で割ったときの余りは$2$である。
$n=k,\,k+1$ のとき$x_{k}$、$x_{k+1}$を$3$で割ったときの余りがともに$2$であると仮定する。このときある整数$a_{k}$、$a_{k+1}$を用いて$$\begin{cases} x_{k+1}=3a_{k+1}+2 \\ x_{k}=3a_{k}+2 \end{cases}$$と表すことができる。これより、$$\begin{align} x_{k+2} &=2(x_{k+1}+x_k) \\ &=2(3a_{k+1}+2+3a_k+2) \\ &=3(2a_{k+1}+2a_{k}+2)+2 \end{align}$$となり、$2a_{k+1}+2a_{k}+2$ は整数であるから$x_{k+2}$を$3$で割ったときの余りは$2$となる。
以上よりすべての正の整数$n$について$x_n$を$3$で割ったときの余りが$2$であることが示された。
□
（２）
方程式$$x^2=2(x+1)$$の解を$\alpha$、$\beta$と置くと漸化式から$$x_{n+2}-(\alpha+\beta)x_{n+1}+\alpha\beta x_n=0$$が成り立つ。これより$$\begin{cases} x_{n+2}-\alpha x_{n+1}=\beta(x_{n+1}-\alpha x_n) \\ x_{n+2}-\beta x_{n+1}=\alpha (x_{n+1}-\beta x_n) \end{cases}$$と式変形できる。それぞれ等比数列の形をしていることから、$$\begin{cases} x_{n+1}-\alpha x_{n}={\beta}^{n-1}(x_{2}-\alpha x_1) \\ x_{n+1}-\beta x_{n}={\alpha}^{n-1} (x_{2}-\beta x_1) \end{cases}$$と求められる。この辺々の差を取って$$(\alpha-\beta)x_n={\beta}^{n-1}(x_{2}-\alpha x_1)-{\alpha}^{n-1}(x_{2}-\beta x_1)$$ $$\therefore 2\sqrt{3}x_n=(1+\sqrt{3})^{n-1}(6+2\sqrt{3})-(1-\sqrt{3})^{n-1}(6-2\sqrt{3})$$ $$\therefore x_n=(1+\sqrt{3})^{n}+(1-\sqrt{3})^{n}$$を得る。これは $n=1$ でも成り立つから求める一般項である。
（答）$x_n=\color{red}{(1+\sqrt{3})^{n}+(1-\sqrt{3})^{n}}$
（３）
（２）より、$$(1+\sqrt{3})^{n}=x_n-(1-\sqrt{3})^{n}$$と表せる。
ここで、$n$が奇数のとき$$-1<(1-\sqrt{3})^{n}<0$$であるから、$(1+\sqrt{3})^n$を越えない最大の整数は $x_{n}-1$ に等しく、この整数を$3$で割ったときの余りは（１）より、$1$である。
また、$n$が偶数のとき$$0<(1-\sqrt{3})^{n}<1$$であるから、$(1+\sqrt{3})^n$を越えない最大の整数は $x_{n}$ に等しく、この整数を$3$で割ったときの余りは（１）より、$2$である。
以上より、$(1+\sqrt{3})^n$を越えない最大の整数を$3$で割ったときの余りは
$n$が奇数のとき$1$、$n$が偶数のとき$2$
となる。
（答）$n$が奇数のとき$1$、$n$が偶数のとき$2$
《コメント》
前問と同様、本問も解と係数の関係に関する整数問題です。$(1-\sqrt{3})^{n}$の絶対値が$1$より小さいことに気が付けばそれまでの誘導設問の意味が理解できると思います。
$2$次方程式の解を$\alpha$、$\beta$とするとき、${\alpha}^n+{\beta}^n$ に関する整数の性質を問う問題はペル方程式に関する問題と並び、難関大の数学で頻出です。実は本問は文系数学で出題されています。「理系のための備忘録」なんていう名前のウェブサイトではありますが、本問の類題は文系の方にもよく訓練しておいてほしいと思います。
（出典：横浜国立大学 1988年）