Fussy's Diary

「アルゴリズムのコーナー」の「画像処理」の章を全てリニューアルしました。主にサンプル・プログラムの見直しを行っています。

「シーム・カービング」は試してみて非常に楽しいアルゴリズムなので、時間があれば他にもいろいろと試してみたいです。また、そのうちに更新を行うかもしれませんが、当分は先の話になりそうです。まだ作ってみたいものは他にもたくさんありますし。

「数学問題bot」から不等式の問題です。最初は手も足も出ない状態でしたが、ふと思い立った方法でなんとか証明してみました。例によって合っている保証はありません。

-----

不等式 (1/2)･(3/4)･(5/6)･ ... ･(999999/1000000) < 1/1000 を示せ ( 第 14 回シュプリンガー数学コンテスト )

命題の証明の前に、二つの補題を証明しておきます。

(補題 1) ( 1 - 1 / n )^-n は単調減少で lim{n→∞} ( 1 - 1 / n )^-n = e

f(x) = ln ( 1 - 1 / x )^-x ( x > 1 ) とすると、

f(x) = -x ln ( 1 - 1 / x ) = -x ln ( x - 1 ) + x ln x

f'(x) = -ln ( x - 1 ) - x / ( x - 1 ) + ln x + 1 = -ln ( x - 1 ) + ln x - 1 / ( x - 1 )

f''(x) = -1 / ( x - 1 ) + 1 / x + 1 / ( x - 1 )²
= [ -x( x - 1 ) + ( x - 1 )² + x ] / x( x - 1 )²
= ( -x² + x + x² - 2x + 1 + x ) / x( x - 1 )²
= 1 / x( x - 1 )² > 0

よって、f'(x) は単調増加です。また、

f'(x) = -ln ( x - 1 ) + ln x - 1 / ( x - 1 )
= ln ( 1 + 1 / ( x - 1 ) ) - 1 / ( x - 1 )
→ 0 ( x → ∞ )

なので f'(x) < 0 となり、f(x) は単調減少となることから ( 1 - 1 / n )^-n も単調減少となります。

ネイピア数の定義より lim{n→∞} ( 1 + 1 / n )ⁿ = e であることを利用すると、

( 1 + 1 / n )ⁿ / ( 1 - 1 / n )^-n
= ( 1 - 1 / n² )ⁿ
= 1 - n( 1 / n² ) + (1/2)n( n - 1 )( 1 / n² )² - ... + (-1)^k_nC_k( 1 / n² )^k + ... → 1 ( n → ∞ )

より lim{n→∞} ( 1 - 1 / n )^-n = e となります。

(補題 2) 関数 ln x に対し、下図において A > B が常に成り立つ



A = ln ( n + 1 ) - ∫{n→n+1} ln x dx
B = ∫{n+1→n+2} ln x dx - ln ( n + 1 )

より

A - B
= ln ( n + 1 ) - ∫{n→n+1} ln x dx - ∫{n+1→n+2} ln x dx + ln ( n + 1 )
= 2ln ( n + 1 ) - ∫{n→n+2} ln x dx
= 2ln ( n + 1 ) - [ x ln x ]{n→n+2} + [ x ]{n→n+2}
= 2ln ( n + 1 ) - ( n + 2 ) ln ( n + 2 ) + n ln n + 2
= ln ( n + 1 )²nⁿe² / ( n + 2 )ⁿ⁺²
= ln [ n / ( n + 2 ) ]ⁿ[ ( n + 1 ) / ( n + 2 ) ]²e²

となります。ここで

[ n / ( n + 2 ) ]ⁿ
= { [ 1 - 2 / ( n + 2 ) ]^(n+2)/2 }²[ ( n + 2 ) / n ]²

より

A - B = ln { [ 1 - 2 / ( n + 2 ) ]^(n+2)/2 }²[ ( n + 1 ) / n ]²e²

となり、補題 1 から { [ 1 - 2 / ( n + 2 ) ]^-(n+2)/2 }² は単調減少で → e² ( n→∞ ) だから、{ [ 1 - 2 / ( n + 2 ) ]^(n+2)/2 }² は単調増加で → 1 / e² ( n→∞ ) となります。また、[ ( n + 1 ) / n ]² → 1 ( n→∞ ) なので、A - B → ln ( 1 / e² )・1・e² = 0 ( n→∞ ) が成り立ちます。

n = 1 のとき、

A - B = ln ( 1 / 3 )( 2 / 3 )²e² = ln ( 4 / 27 )e² > ln ( 4 / 27 )( 2.7 )² = ln 1.08 & gt; 0

なので、A - B が n の増加に対して単調減少であれば常に正であることになります。そこで、

f(x) = 2ln ( x + 1 ) - ( x + 2 ) ln ( x + 2 ) + x ln x + 2 ( x ≥ 1 )

とすると、

f'(x)
= 2 / ( x + 1 ) - ln ( x + 2 ) - 1 + ln x + 1
= 2 / ( x + 1 ) - ln ( x + 2 ) + ln x

f''(x)
= -2 / ( x + 1 )² - 1 / ( x + 2 ) + 1 / x
= [ -2x( x + 2 ) - x( x + 1 )² + ( x + 1 )²( x + 2 ) ] / x( x + 1 )²( x + 2 )
= [ -2x² - 4x + 2( x + 1 )² ] / x( x + 1 )²( x + 2 )
= 2 / x( x + 1 )²( x + 2 ) > 0

なので f'(x) は単調増加で、x = 1 のとき f'(1) = 1 - ln 3 > 0、f'(x) = 2 / ( x + 1 ) + ln ( 1 - 2 / ( x + 2 ) ) → 0 ( x→∞ ) だから、f'(x) < 0 が成り立ちます。よって f(x) は単調減少で、f(x) > 0 が常に成り立つことが証明されました。

(証明)

ln (1/2)･(3/4)･(5/6)･ ... ･(999999/1000000) = ( ln 1 + ln 3 + ... + ln 999999 ) - ( ln 2 + ln 4 + ... + ln 1000000 )

と変形できるので、左辺の二つの項についてその大きさを調べてみます。



上図の上側の ln x と台形との面積の大きさを比較すると、

2( ln 1 + ln 3 ) / 2 + 2( ln 3 + ln 5 ) / 2 + ... 2( ln 999997 + ln 999999 ) / 2 < ∫{1→999999} ln x dx

が成り立ちます。この式は

ln1 + 2( ln 3 + ln 5 + ... + ln 999997 ) + ln 999999 < ∫{1→999999} ln x dx

と変形できて、ln 1 = 0 だから

ln1 + ln 3 + ln 5 + ... + ln 999997 + ln 999999 < (1/2)( ∫{1→999999} ln x dx + ln 999999 )

が成り立ちます。また、図の下側と補題 2 から

2 ln 2 + 2 ln 4 + 2 ln 6 + ... + ln 1000000 > ∫{1→1000000} ln x dx

なので、

ln 2 + ln 4 + ln 6 + ... + ln 1000000 > (1/2)( ∫{1→1000000} ln x dx + ln 1000000 )

となります。よって、

( ln 1 + ln 3 + ... + ln 999999 ) - ( ln 2 + ln 4 + ... + ln 1000000 ) < (1/2)( ∫{1→999999} ln x dx + ln 999999 - ∫{1→1000000} ln x dx + ln 1000000 )

ここで 1000000 = M, 999999 = m として右辺を変形すると

(右辺) = (1/2)[ ln ( m / M ) - ∫{m→M} ln x dx ]

∫{m→M} ln x dx
= [ x ln x ]{m→M} - &int{m→M} dx
= ln ( M^M / m^m ) - ( M - m )
= ln ( M^M / m^m ) - 1

よって

(右辺)
= (1/2)[ ln ( m / M ) - ln ( M^M / m^m ) + 1 )
= (1/2) ln ( m^mme / M^MM )
= (1/2) ln ( ( m / M )^M( e / M ) )
= (1/2) ln ( ( 1 - 1 / M )^M( e / M ) )

となります。補題 1 から

( 1 - 1 / M )^M = 1 / ( 1 - 1 / M )^-M → 1 / e ( M→∞ )

であり、( 1 - 1 / M )^-M は単調減少だから ( 1 - 1 / M )^-M > e より ( 1 - 1 / M )^M < 1 / e となって、

( ln 1 + ln 3 + ... + ln 999999 ) - ( ln 2 + ln 4 + ... + ln 1000000 )
< (1/2)( ∫{1→999999} ln x dx + ln 999999 - ∫{1→1000000} ln x dx + ln 1000000 )
< (1/2)ln 1 / 1000000 = ln ( 1 / 1000 )

よって、不等式が証明されました。