問題
2つの数列，は，および，関係式
をみたすものとする．
(1) のとき，は3で割り切れるが，は3で割り切れないことを示せ．
(2) のとき，とは互いに素であることを示せ．
出典：九州大学 2006年度 前期日程 第2次学力試験 文系 第2問
方針
(1)はまず を計算し，3で割った余りの帰納法に入る。 が3の倍数で が3の倍数でないなら，次も は3の倍数， は と同じ余りになる。(2)は が常に奇数であることを先に示し，共通素因数が2でないようにしてから， と で矛盾を作る。
解答
(1)
初めの値を計算すると である。さらに である。したがって は3で割り切れ， は3で割り切れない。 において， は3で割り切れ， は3で割り切れないと仮定する。このとき であるから， は3で割り切れる。また であり， は3で割り切れるので である。 は3で割り切れないから，3で割った余りは1または2であり， の余りは1である。したがって は3で割り切れない。よって数学的帰納法により， で主張が成り立つ。
(2)
まず はすべて奇数であることを示す。 は奇数であり， が奇数なら の第1項は偶数，第2項は奇数なので， も奇数である。したがってすべての で は奇数である。 ， は互いに素である。ある で と が互いに素であると仮定し， と が共通の素因数 を持つとする。 は奇数なので， である。 は を割り， だから， は または を割る。もし なら， と より ，したがって となる。これは が互いに素であることに反する。もし なら，同じ式から であり， なので となって，やはり矛盾する。
したがって と も互いに素である。数学的帰納法により， で と は互いに素である。