(N/m)^m を最大にするmはN/eを四捨五入して得られる
由来: http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13150857338
由来の由来: http://hagure.my.coocan.jp/ の「執務室」に書かれた問題に対して
2015/10/24に作成されたノートです
・2023/04/27 半角不等号が適切に表示されていないことに気づき全角にした
【命題】
Nを自然数とする。
(N/m)^m を最も大きくするような自然数mを n とすると
n は N/e を四捨五入して求めることができる。(e:自然対数の底)
証明をいくつかの段階に分ける。
【1】次の形の主張をすることができる:
「n≧A の範囲で反例が存在すると仮定すると Q=2n+1 に対して
|e-2M/Q|*Q^2 < C を満たす整数Mが存在する」
ここで A,Cは定数であり A=15, C=0.475 をとることができる。
【2】2M/Q が eの最良近似分数である場合を考慮すれば十分であることを示す。
eの最良近似分数とは以下の数列の要素である。
{R[1],R[2],...} = {1/0,2/1,3/1,8/3,11/4,19/7,87/32,106/39,193/71,1264/465,1457/536,2721/1001,23225/8544...}
【3】jが十分大きければ eはR[3j+1]とR[3j+2]をほぼ1:1に分けることを示す。
ここでeの連分数展開を証明なしに使う。
【4】以上を使って命題を証明する。
【1】
a[n]=(n+1)^(n+1)/n^n, b[n]=(n+1/2)e とおく。これらは整数をとらない。
(N/m)^m < (N/(m+1))^(m+1) ⇔ a[m] < N より
m=nのとき (N/m)^m は最大となる ⇔ a[n-1]<N<a[n]
一方
nは N/eを四捨五入して得る ⇔ b[n-1]<N<b[n]
従ってすべてのnに対して a[n]とb[n]の整数部分が等しい、
すなわちa[n]とb[n]が決して整数を挟まないことを示せば良い。
------------------------
(1+x)^(1/x)のテイラー展開を考えて以下の不等式を得る
e(1-x/2+11x^2/24-7x^3/16) < (1+x)^(1/x) < e(1-x/2+11x^2/24)
x=1/n とおいて各辺に(n+1)を掛けると以下の評価を得る
(n+1/2-1/24n+1/48n^2-7/16n^3)e < a[n] < (n+1/2-1/24n+11/24n^2)e
この評価から a[n] < b[n] の関係が判明し、
a[n]とb[n]が整数を挟まないことを示すには
上の不等式の左辺とb[n]が整数を挟まないこと、すなわち
(n+1/2-1/24n+1/48n^2-7/16n^3)e < M < b[n]
となるn,Mが存在しないことを示せば十分である。
以下これを満たすようなn,Mが存在すると仮定する。
2n+1 = Q とおいて変形
0 < (e-2M/Q)Q^2 < (2Q^2-6Q+88)MQ/(6Q^4-18Q^3+17Q^2-3Q-44)
左側より得る M < Qe/2 を右側に適用する。
右辺 < (2Q^2-6Q+88)(Qe/2)Q/(6Q^4-18Q^3+17Q^2-3Q-44)
= e/6 * {1+(247Q^2+3Q+44)/(6Q^4-18Q^3+17Q^2-3Q-44)}
0 < (e-2M/Q)Q^2 < e/6 * {1+(247Q^2+3Q+44)/(6Q^4-18Q^3+17Q^2-3Q-44)}
を満たす整数Mおよび3以上の奇数Qが存在することが要求される。
右辺は Qが十分大きい時単調減少であることが分かる。
そこで適当にQ=31 ぐらいを代入すると右辺は 0.4744... となるから
「n≧15 の範囲で反例が存在すると仮定すると
|e-2M/Q|*Q^2 < 0.475 を満たす整数M,Qが存在する」 が言える。
(N/m)^m を最も大きくするような自然数mは
N/e の前後のどちらかの整数であることは別の議論で分かっているから
n≦15の範囲はN≦43の範囲に相当し、
この有限範囲に反例が存在しないことは計算で確かめられる。
【2】
|e-P/Q| * Q^2 < 0.475 ・・・★
となる整数P,Qを探すという視点で考察する。
【2−1】対
eをはさむ2つの分数 P/Q と P'/Q' (Q<Q')の間に
分母がQより小さい分数が存在しないとき
<P/Q,P'/Q'> を「(eをはさむ)対」と呼ぶことにする。
(この記法で書く時、P/QとP'/Q'の大小は問わない)
このとき次が成り立つ:
[1] |QP'-PQ'|=1 となる。すなわち |P'/Q'-P/Q| = 1/QQ' となる。
[2] P''/Q'' = (P+P')/(Q+Q') とおく。
P/Q < e < P''/Q'' または P''/Q'' < e < P'/Q' のどちらかが成り立ち
それは eをはさむ対となる
[3] P/Q = 0/1, P'/Q'=1/0 から始めて[2]の操作を繰り返せばeをはさむ対をすべて得る
これらの性質は http://mathtrain.jp/farey などを参照せよ。
[3]は無限降下法的に示されるだろう。
★を満たす分数P/Qがあったとしたら
eとP/Qの間にある分母がより小さい分数P'/Q' (Q'<Q) を採用しても
左辺は小さくなる方向であり★を満たすので
「eをはさむ対」に現れる分数を考慮すれば十分である。・・ように思われるが
少し注意点がある。
元の問題に適するにはPが偶数という条件がある。Q≧31 という条件もある。
上記の場合にP'が奇数あるいはQ'<31のため P'/Q' が不採用になった際に
外側のP/Qを考慮する必要があるかどうかを言及しておく必要があるだろう。
実は考慮不要である。なぜなら:
|P/Q-e|*Q^2 > |P/Q-P'/Q'|*Q^2 ≧ (1/QQ')*Q^2 = Q/Q' > 1 > c で★を満たさない。
-----------
【2−2】最良対
P[0]/Q[0]=0/1, P[1]/Q[1]=1/0 とおく。
<P[k]/Q[k], P[k+1]/Q[k+1]>, から P[k+2]/Q[k+2]およびM[k]を次のように定める:
<(P[k]+mP[k+1])/(Q[k]+mQ[k+1]), P[k+1]/Q[k+1]> がeをはさむ対となる最大のmをM[k]と定め
そのときの(P[k]+mP[k+1])/(Q[k]+mQ[k+1])を P[k+2]/Q[k+2] と定める。
これによりeをはさむ対の部分集合{<P[k]/Q[k],P[k+1]/Q[k+1]>}を得る:
これで得られる対を「最良対」と呼ぶことにする。
k番目の最良対と順序づけて書きだしておく:
k=0: <0/1, 1/0>, M=2
k=1: <1/0, 2/1>, M=1
k=2: <2/1, 3/1>, M=2
k=3: <3/1, 8/3>, M=1
k=4: <8/3, 11/4>, M=1
k=5: <11/4, 19/7>, M=4
k=6: <19/7, 87/32>, M=1
k=7: <87/32, 106/39>, M=1
k=8: <106/39,193/71>, M=6
k=9: <193/71, 1264/465>, M=1
k=10: <1264/465, 1457/536>, M=1
k=11: <1457,536, 2721/1001>, M=8
k=12: <2721/1001, 23225/8544> ...
------------
【2−3】
★を調べるには P/Q が最良対の場合だけを考慮すれば良いことを示す。
r(m) = p(m)/q(m) = (P[k]+mP[k+1])/(Q[k]+mQ[k+1]) とおく。
m≦M[k] の範囲なら r(m)とP[k+1]/Q[k+1]がeをはさむ大小関係である。
(e-r(m)) * q(m)^2
= (|P[k+1]/Q[k+1]-r(m)| - |P[k+1]/Q[k+1]-e|) * q(m)^2
= q(m)/Q[k+1] - |P[k+1]/Q[k+1]-e|*q(m)^2
m=M[k]のときにこの値が最も小さくなることを言えば良い。
式はq(m)の最高次係数が負である2次関数であり
q(m) が軸 1/2 * 1/Q[k+1] * 1/|P[k+1]/Q[k+1]-e| から離れるほど小さい
軸が q(M[k]) より小さいことを確認すれば良い。
P[k]/Q[k] < p(m)/q(m) < e < p(M[k]+1)/q(M[k]+1) < P[k+1]/Q[k+1]
という大小関係に注意して
1/2 * 1/Q[k+1] * 1/|P[k+1]/Q[k+1]-e|
< 1/2 * 1/Q[k+1] * 1/|P[k+1]/Q[k+1]-p(M[k]+1)/q(M[k]+1)|
= 1/2 * q(M[k]+1)
= Q[k]/2 + (M[k]+1)Q[k+1]/2
< Q[k] + (M[k]+M[k])Q[k+1]/2 = q(M[k]) で示された。
【3】
k=3N+1でNが十分大きければ eはR[k]とR[k+1]をほぼ1:1に分けることを示す。
具体的には |P[k]/Q[k]-e| : |P[k+1]/Q[k+1]-e| = s[k]:t[k] (s[k]+t[k]=1)
とおいてt[3N+1] を評価する。
既に定義したM[k]は連分数近似に現れる数列と一致する。
eの連分数近似に現れる数列は
2;1,2,1,1,4,1,...,1,2i,1,...と規則的に振舞うことが知られている。
このことの証明はここでは与えられない。
s[k+1] = |e-P[k+1]/Q[k+1]|/|P[k+2]/Q[k+2]-P[k+1]/Q[k+1]|
= (t[k] / Q[k]Q[k+1])/(1/Q[k+1]Q[k+2])
= t[k] * Q[k+2]/Q[k]
という関係が成り立つ。あるいは t[k] = s[k] / (Q[k+2]/Q[k])
Q[k+2]/Q[k] = (Q[k]+M[k]Q[k+1])/Q[k]
= 1+M[k]*(Q[k-1]+M[k-1]Q[k])/Q[k]
= 1 + M[k]M[k-1] + M[k]*{Q[k-1]/(Q[k-2]+M[k-2]Q[k-1])}
ここで 0 < {Q[k-1]/(Q[k-2]+M[k-2]Q[k-1])} < 1/M[k-2] によって
式全体を評価し、それを先の式に当てはめて t[k]の次の評価を得る:
s[k+1]/(1+M[k]/M[k-2]+M[k]M[k-1]) < t[k] < s[k+1]/(1+M[k]*M[k-1]) ・・・@
0<s[k+1]<1 を@に適用して 0 < t[k] < 1/(1+M[k]*M[k-1]) を得る。
kを1個ずらして1から引くことで 1-1/(1+M[k]M[k+1]) < 1-t[k+1] = s[k+1] < 1
これを再度@に適用して (1-1/(1+M[k]M[k+1]))/(1+M[k]/M[k-2]+M[k]M[k-1]) < t[k] < 1/(1+M[k]*M[k-1])
ここで k=3j+1を代入、連分数の規則より M[k-1]=M[k]=1, M[k+1]=2j+2,M[k-2]=2j を適用すると
(1 - 1/(2j+3)) / (1+1/2j+1) < t[3j+1] < 1/2
整理して (4j^2+4j)/(8j^2+14j+3) < t[3j+1] < 1/2
左辺は 1/2 に下から近づく。
【4】
kが3の倍数でなければkがある程度大きければ
★を満たすP[k]/Q[k]は存在しない。これは【4−1】【4−2】で示す。
一方kが3の倍数の時にはP[k]/Q[k]は★を満たすがP[k]は奇数となる。
(P[k]の偶奇の振る舞いは周期的なので調べれば確認できる)
その周辺の分子が偶数となる分数を調べる必要がないことは【2−1】で述べた。
【4−1】k=3j+1 のとき
|e-P[k]/Q[k]|*Q[k]^2 = s[k] * |P[k+1]/Q[k+1]-P[k]/Q[k]|*Q[k]^2
= s[k] *(1/Q[k+1]Q[k])*Q[k]^2 = s[k]*Q[k]/Q[k+1] を利用する。
先の【3】の結果から t[3j+1] < 1/2 なので s[3j+1] > 1/2 が分かっている。
Q[k]/Q[k+1] が 1に近づくことを示す必要がある。
M[k-1]=1, M[k-2]=2j を利用する。
Q[k]/Q[k+1] = Q[k]/ (Q[k-1]+M[k-1]Q[k])
= 1/ (Q[k-1]/Q[k] + 1)
= 1/ {(Q[k-1]/(Q[k-2]+M[k-2]Q[k-1]) + 1}
= 1/ { 1/(2j+Q[k-2]/Q[k-1]) + 1}
0 < Q[k-2]/Q[k-1] < 1 より式全体を評価して
Q[k]/Q[k+1] > 2j/(2j+1) が言える。
数値計算により j≧10 なら s[k]*Q[k]/Q[k+1] > j/(2j+1) > C が言えて
先の利用により ★が成り立つことが従う。
【4−2】
同様に |e-P[k+1]/Q[k+1]|*Q[k+1]^2 = t[k]*Q[k+1]/Q[k] を利用する。
Q[k+1]/Q[k] > 1 より t[k] > C を言えば十分である。
先の【3】の結果 t[k] > (4j^2+4j)/(8j^2+14j+3) を数値計算すれば
j≧15 なら t[k] > C が成り立ち、よって★が成り立つ。
【4−3】
j≦9 のときの P[3j+1]/Q[3j+1], j≦14 のときの P[3j+2]/Q[3j+2] が残るが
実際に個別に |e-P[k]/Q[k]|*Q[k]^2 を計算すれば、
k=4 を除いて C=0.475 より大きいことが分かる。
k=4 では Q[k]=3なのでQ<31として除外される。
以上により証明は終了した。
参考:
d(k) = (e-P[k]/Q[k])*Q[k]^2 (k≧2)
[k, P[k]/Q[k], d(k)]
[2, 2, 0.71828..]
[3, 3, -0.28171..]
[4, 8/3, 0.46453..]
[5, 11/4, -0.50749..]
[6, 19/7, 0.19580..]
[7, 87/32, -0.47940..]
[8, 106/39, 0.50666..]
[9, 193/71, -0.14130..]
[10, 1264/465, 0.48835..]
[11, 1457/536, -0.50381..]
[12, 2721/1001, 0.11039..]
[13, 23225/8544, -0.49252..]
[14, 25946/9545, 0.50246..]
[15, 49171/18089, -0.09052..]
[16, 517656/190435, 0.49479..]
[17, 566827/208524, -0.50174..]
[18, 1084483/398959, 0.07666..]
戻る