Mathematics
Examination
Test
Archives
【4】 を自然数とする.種類の文字を用いて長さの文字列を作ることを考える.このような文字列のうち,以下の条件を満たすものを禁止文字列と呼ぶ.
条件:文字がこの順に連続kして現れない.
たとえば,長さの文字列は禁止文字列であるが,は禁止文字列ではない.長さの禁止文字列の個数をと書く.たとえば,長さの文字列はすべて禁止文字列だからであり,長さの文字列はを除いてすべて禁止文字列だからである.以下の問いに答えよ.
(1) 長さの禁止文字列のうち,末尾がのものの個数をとおく.同様に末尾が末尾がであるような長さの禁止文字列の個数をそれぞれとおく.このとき,三つの等式
が成り立つ.理由を説明せよ.
(2) 等式
が成り立つことを示せ.
(3) 二次方程式
の解を(ただし)とおく.等式
および
が成り立つことを示せ.
(4) 極限
を調べよ.