問題
箱の中に，1から までの数字をそれぞれ1つずつ書いた 枚のカードが入っている．箱から無作為に1枚のカードを取り出して，その数字を記録し，箱に戻す．この試行を 回くり返し，それまでに記録された相異なる数字の個数を とする． となる確率を で表すとき，次の問に答えよ．
(1) を と で表せ．
(2) の期待値 を求めよ．
出典：東京工業大学 1989年度 前期 理系 第5問
方針
第 回の直前に記録済みの種類数が のまま変わらない場合と， から1つ増える場合に分ける。(2) は(1)の漸化式に を掛けて和をとり，添字をそろえて を導く。最後に等比型の1次漸化式を解く。
解答
(1)
第 回の試行後に となるには，次の2通りがある。
まず，第 回までに相異なる数字が 個あり，第 回にその中のどれかを引く場合である。この確率は である。
次に，第 回までに相異なる数字が 個あり，第 回にまだ出ていない数字を引く場合である。このとき未出の数字は 個あるから，確率は である。
したがって
である。ただし，範囲外の に対する確率は とみなす。
(2)
(1) の式に を掛け， について和をとる。範囲外の確率を とみなせば
また である。よってとなるから，
である。