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

シルベスターの数列(Sylvester's sequence)

a0=2,an+1=an2an+1a_0=2, a_{n+1}=a_n^2-a_n+1

で定義される数列をシルベスターの数列と言う。

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

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

シルベスター数列の正体をつかむために,nn が小さい場合について実験してみると,

a0=2,a1=3,a2=7,a3=43, a_0=2,a_1=3,a_2=7,a_3=43,\cdots

となります。

鋭い人は以下の規則性に気づくでしょう。

7=1+2343=1+237\begin{aligned} 7&=1+2\cdot 3\\ 43&=1+2\cdot 3\cdot 7 \end{aligned}

実は,以下の性質1が成立します。

性質1

任意の 00 以上の整数 nn について, an=1+k=0n1ak a_n=1+\displaystyle\prod_{k=0}^{n-1}a_k が成り立つ。

ただし,k=0n1ak\displaystyle\prod_{k=0}^{n-1}a_ka0a_0 から an1a_{n-1} までの積を表します。n=0n=0 のときは(空集合の積は 11 とみなして) 11 とみなします。→総積の記号Π(パイ)の意味と性質

証明

数学的帰納法で簡単に証明できる。

n=0n=0 のときは両辺ともに 22 となり成立。

また,n=kn=k のときを仮定すると,

ak+1=ak2ak+1=(1+i=0k1ai)2i=0k1ai=i=0k1ai(i=0k1ai+1)+1=i=0kai+1\begin{aligned} a_{k+1} &= a_k^2-a_k+1\\ &=(1+\prod_{i=0}^{k-1}a_i)^2-\prod_{i=0}^{k-1}a_i\\ &=\prod_{i=0}^{k-1}a_i(\prod_{i=0}^{k-1}a_i+1)+1\\ &=\prod_{i=0}^{k}a_i+1 \end{aligned}

となり n=k+1n=k+1 のときも成立する。

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

フェルマー数との関係

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

性質2

n1n\geq 1 のとき 22n1<an<22n2^{2^{n-1}} <a_n <2^{2^n}

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

誘導付きで難関大学の入試で出題されそうなレベルの問題です。

記号はゴツイですが難しい計算はありません。「m,nm,n が整数のとき m<n+1m < n+1mnm\leq n が同値である」ことを用います。

証明

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

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

  1. Fn11<an<Fn1F_{n-1}-1 < a_n < F_{n}-1

  2. k=0n2Fk<k=0n1ak<k=0n1Fk\displaystyle\prod_{k=0}^{n-2}F_k <\prod_{k=0}^{n-1}a_k <\prod_{k=0}^{n-1}F_k

これを帰納法で示す。 nn のとき1も2も成立していると仮定すると,

2の不等式の各辺に ana_{n} をかけて,

ank=0n2Fk<k=0nak<ank=0n1Fk a_{n}\prod_{k=0}^{n-2}F_k <\prod_{k=0}^{n}a_k <a_{n}\prod_{k=0}^{n-1}F_k

これに1を用いると(左側の不等式は整数性に注意して Fn1anF_{n-1} \leq a_n とより強い不等式を用いる)

k=0n1Fk<k=0nak<k=0nFk \prod_{k=0}^{n-1}F_k <\prod_{k=0}^{n}a_k <\prod_{k=0}^{n}F_k

となり n+1n+1 のときも2が成立することが示された。

頻出の整数問題(Egyptian fraction)

性質3

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

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

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

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

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

また,単位分数については エジプト分数(単位分数の和)に関する4つの話題 もどうぞ。

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

Tag:数学的帰納法をわかりやすく【例題3問、応用5パターン】