作問の備忘録

テスト問題を作るときの、大した計算ではないけれども、やろうと思うとめんどくさいことどもを記録。

３行の互除法の作問(ある程度解決)

互除法

～続いた～

別の方向からある程度解決したので書いていく。

ひたすらいろんな数を試した結果、フィボナッチがどうとかいう問題ではなく、

$F_n=(r+1)r^n-(-1)^n (rは2以上の自然数)$

の形の数列が畳数3であることが分かった。

証)　

$F_n=(r+1)\cdot r^n-(-1)^n$ に対し、

$F_{2k}=(r-1)F_{2k-1}+\{ F_{2k-1}-(r+1) \}$ を示す。

$(右辺)=rF_{2k-1}-(r+1)$

$\hspace{2.7em}=(r+1)r^{2k}-r(-1)^{2k-1}-(r+1)$

$\hspace{2.7em}=(r+1)r^{2k}+r-r-1$

$\hspace{2.7em}=(r+1)r^{2k}-1$

$\hspace{2.7em}=(r+1)r^{2k}-(-1)^{2k}$

$\hspace{2.7em}=F_{2k}$

また、

$F_{2k-1}=\{ F_{2k-1}-(r+1) \}+(r+1)$

ここで、 $F_{2k-1}-(r+1)-(r+1)=(r+1)r^{2k-1}-2r-1$

$r\geqq2, k\geqq 1$ なので，明らかに正。

このとき、余りは $r+1$ である。

$F_{2k-1}-(r+1)=(r+1)r^{2k-1}-(-1)^{2k-1}-(r+1)$

$\hspace{6.75em}=(r+1)r^{2k-1}-r$

$\hspace{6.75em}=(r+1)r^{2k-1}-(r+1)+1 \equiv 1 (\bmod r+1)$

次に、

$F_{2k+1}=rF_{2k}+(r+1)$ を示す。

$(右辺)=rF_{2k}+(r+1)$

$\hspace{2.7em}=r\{(r+1)r^{2k}-(-1)^{2k}\}+r+1$

$\hspace{2.7em}=(r+1)r^{2k+1}-r+r+1$

$\hspace{2.7em}=(r+1)r^{2k+1}+1$

$\hspace{2.7em}=F_{2k+1}$

また、

$F_{2k+1}=rF_{2k}+(r+1)$ において、

$F_{2k}-(r+1)=(r+1)r^{2k}-r-2$

明らかに正。

余りは $r+1$

$F_{2k}=(r+1)r^{2k}-(-1)^{2k}$

$\hspace{1.75em}=(r+1)r^{2k}-1$

$\hspace{1.75em}=(r+1)r^{2k}-(r+1)+r \equiv r (\bmod r+1)$

以上より、

$F_n=(r+1)r^n-(-1)^n$ の隣り合う２項は畳数3となる。