2016年10月23日

不等式の問題

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

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

数学問題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 )2
= [ -x( x - 1 ) + ( x - 1 )2 + x ] / x( x - 1 )2
= ( -x2 + x + x2 - 2x + 1 + x ) / x( x - 1 )2
= 1 / x( x - 1 )2 > 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 )n = e であることを利用すると、

( 1 + 1 / n )n / ( 1 - 1 / n )-n
= ( 1 - 1 / n2 )n
= 1 - n( 1 / n2 ) + (1/2)n( n - 1 )( 1 / n2 )2 - ... + (-1)knCk( 1 / n2 )k + ... → 1 ( n → ∞ )

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

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

補題2の図

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 )2nne2 / ( n + 2 )n+2
= ln [ n / ( n + 2 ) ]n[ ( n + 1 ) / ( n + 2 ) ]2e2

となります。ここで

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

より

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

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

n = 1 のとき、

A - B = ln ( 1 / 3 )( 2 / 3 )2e2 = ln ( 4 / 27 )e2 > ln ( 4 / 27 )( 2.7 )2 = 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 )2 - 1 / ( x + 2 ) + 1 / x
= [ -2x( x + 2 ) - x( x + 1 )2 + ( x + 1 )2( x + 2 ) ] / x( x + 1 )2( x + 2 )
= [ -2x2 - 4x + 2( x + 1 )2 ] / x( x + 1 )2( x + 2 )
= 2 / x( x + 1 )2( 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)と台形・矩形の大きさ比較

上図の上側の 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 ( MM / mm ) - ( M - m )
= ln ( MM / mm ) - 1

よって

(右辺)
= (1/2)[ ln ( m / M ) - ln ( MM / mm ) + 1 )
= (1/2) ln ( mmme / MMM )
= (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 )

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

Posted by fussy at 18:02Comments(0)TrackBack(0)数学