問題
を自然数とする．個の箱すべてに，1，2，3，4，5の5種類のカードがそれぞれ1枚ずつ計5枚入っている．各々の箱から1枚ずつカードを取り出し，取り出した順に左から並べて桁の数を作る．このとき，が3で割り切れる確率を求めよ．
出典：京都大学 2017年度 前期日程 第2次学力試験 理系 第6問
方針
3で割り切れるかどうかは桁和の3で割った余りだけで決まる。各箱から出るカードの余りは，0が1種類，1が2種類，2が2種類である。桁までの桁和の余りが0である列数を，余り1と余り2である列数を対称性によりともにとおく。と，次の1枚を加えたときのから漸化式を作り，を求める。
解答
整数が3で割り切れるかどうかは，各桁の和が3で割り切れるかどうかで決まる。カードを3で割った余りで分類すると である。 枚取り出して並べたとき，桁和を3で割った余りが0となる並べ方の数をとする。また，余り1となる並べ方の数と余り2となる並べ方の数は，余り1と余り2のカードの種類数がどちらも2であることから等しい。これをとおく。すると である。
次に1枚を追加して，余り0になる場合を数える。前の余りが0で，余り0のカードを加える場合が通りある。前の余りが1で，余り2のカードを加える場合は，余り2のカードが2種類あるので通りである。前の余りが2で，余り1のカードを加える場合も通りである。したがって である。 を代入すると である。初期値は，1桁で余り0となるカードが3だけなので である。
この漸化式を解く。式 に対して， が成り立つことは，で正しく，さらに代入により次の項でも成り立つので帰納的に確認できる。
全体の並べ方は通りである。したがって求める確率は である。