2014/05/30

シルベスターの数列とその性質

分野: 数列  レベル: マニアック

$a_0=2, a_{n+1}=a_n^2-a_n+1$
で定義される数列をシルベスターの数列と言う


シルベスターの数列は非常に有名な数列の1つです。入試では整数問題の題材としてたまに取り上げられます。

シルベスターの数列の規則性

シルベスター数列の正体をつかむために $n$ が小さい場合について実験してみると,
$a_0=2,a_1=3,a_2=7,a_3=43\cdots$
となります。

鋭い人は規則性があることに気づくでしょう。(入試問題としてちょうどよいレベルの問題だと思います)
$7=1+2\cdot 3\\43=1+2\cdot 3\cdot 7$

性質1: $a_n=1+\displaystyle\prod_{k=0}^{n-1}a_k$

証明

数学的帰納法で簡単に証明できる:
$n=0$ のときは(空集合の積は $1$ と定義するので)$a_0=2$ となり成立。
また,$n=k$ のときを仮定すると,
$a_{k+1}=a_k^2-a_k+1\\
=(1+\displaystyle\prod_{i=0}^{k-1}a_i)^2-\prod_{i=0}^{k-1}a_i\\
=\displaystyle\prod_{i=0}^{k-1}a_i(\prod_{i=0}^{k-1}a_i+1)+1\\
=\displaystyle\prod_{i=0}^{k}a_i+1$
となり $n=k+1$ のときも成立する。

性質1をシルベスター数列の定義として定義を性質とみなすこともできます。

フェルマー数との関係

性質1の式がフェルマー数($F_n=2^{2^n}+1$)の性質1と似ている(→フェルマー数とその性質)ことに気づくと以下のように面白い不等式が導けます。

性質2: $n\geq 1$ のとき $2^{2^{n-1}} <a_n <2^{2^n}$

これより,シルベスターの数列は二重指数的に増加していくことが分かります。

誘導付きで難関大学の入試で出題されそうなレベルの問題です。
記号はゴツイですが難しい計算はありません。「 $m,n$ が整数のとき $m <n+1$ と $m\leq n$ が同値である」ことを用いるのが最もテクニカルです。

証明

$n=1$ のとき,$2 <a_1 <4$ より正しい。

フェルマー数の性質($F_n=\displaystyle\prod_{k=0}^{n-1}F_k+2$)と上記の性質1を用いると示すべき不等式は,以下のように2通りでかける(同値な不等式)
1:$F_{n-1}-1 <a_n <F_{n}-1$
2:$\displaystyle\prod_{k=0}^{n-2}F_k <\prod_{k=0}^{n-1}a_k <\prod_{k=0}^{n-1}F_k$

これを帰納法で示す。 $n$ のとき1も2も成立していると仮定すると,
2の不等式の各辺に $a_{n}$ をかけて,
$a_{n}\displaystyle\prod_{k=0}^{n-2}F_k <\prod_{k=0}^{n}a_k <a_{n}\prod_{k=0}^{n-1}F_k$
これに1を用いると(左側の不等式は整数性に注意して $F_{n-1} \leq a_n$ とより強い不等式を用いる)
$\displaystyle\prod_{k=0}^{n-1}F_k <\prod_{k=0}^{n}a_k <\prod_{k=0}^{n}F_k$
となり $n+1$ のときも2が成立することが示された。

頻出の整数問題(Egyptian fraction)

性質3:$M=\displaystyle\sum_{k=1}^n\dfrac{1}{a_k} <1$ を満たす自然数 $a_1,a_2,\cdots,a_n$ の組で,$M$ の最大値を与えるのは $a_n$ がシルベスター数列(またはその並べ替え)のとき

$n=2,3$ のときはよくある入試問題です。いずれも場合分けで解くことができます。

$\dfrac{1}{a_1}+\dfrac{1}{a_2} <1, a_1 <a_2$ を満たす自然数 $a_1,a_2$ に対して $\dfrac{1}{a_1}+\dfrac{1}{a_2}$ が最大となるのは $a_1=2,a_2=3$ のときでその値は $\dfrac{5}{6}$

$\dfrac{1}{a_1}+\dfrac{1}{a_2}+\dfrac{1}{a_3} <1, a_1 <a_2 <a_3$ を満たす自然数 $a_1,a_2,a_3$ に対して $\dfrac{1}{a_1}+\dfrac{1}{a_2}+\dfrac{1}{a_3}$ が最大となるのは $a_1=2,a_2=3,a_3=7$ のときでその値は $\dfrac{41}{42}$

一般の $n$ に対する性質3の証明は複雑なので省略します。例えば→単位分数のエジプト分数による下からの近似を参照して下さい。

世の中にはいろいろな数列がありますねえ。

Tag: 数学的帰納法のパターンまとめ

分野: 数列  レベル: マニアック