📝 問題
集合,を，とし，を以上の整数とする．また，各項がまたはからなる数列を数列と呼ぶことにする．
数列に対し，からへの写像を用いて，新しい数列を，
と定め，,,,は,,,からによって得られるという．ただし，からへの写像とは，の各要素にたいしての要素をただひとつ対応させる規則をさすものとする．次の問に答えよ．
-
からへの写像は，全部で何通りあるか．
-
，，であるとき，
となるような数列，，，を求めよ．
-
からへの写像が，条件
を満たすとする．このようなは何通りあるか．
-
からへの写像が条件(P)をみたすならば，どのような項からなる数列も，ある数列,,,からによって得られることを示せ．
【解答】
(1)
の 1 つの要素に対し の 通りの写像のつくり方があるから 通りである．(答)
(2)
題意のはが偶数で，奇数でなる数列
である．
まず，で成立する条件を調べる．
与式の漸化式より
であり，は題意より
だから，
と初項が定まる．
漸化式はの偶奇に応じて
をみたす．
従って，を代入して(式5)より
であり，はまたはだから
である．
以下，帰納的に
であることを示す．
の時は(式5),(式9)より成立するから，
以下を自然数としてでの成立を仮定して，
での成立を示す．
(式6)の漸化式より
となりたしかに成立する．
以上から，数学的帰納法によっての一般項は
である． (答)
(3)
の要素は つだけだから，各 に対し，, の定め方は 通りである．
従って，求める場合の数はに対して通りづつで
通りである． (答)
(4)
についての数学的帰納法で示す．
での成立は明らかなので，以下 での成立を仮定して での成立を示す．
この時仮定から任意の01数列 はある01数列に写像を適用して作ることができる．
そして 項目について漸化式より
であり，法の合同式で考えると
である．
条件(P)よりは引数の偶奇によってももとることができるから，
の値によらずをかで調整すれば欲しいが得られる．
よっての場合でも題意は成立する．
以上より，数学的帰納法によって題意は示された．(答)
【解説】
