Quod Erat Demonstrandum

2008/07/18

錯在哪裡之數學歸納法

Filed under: Additional / Applied Mathematics,HKCEE — johnmayhk @ 10:11 下午

對於任意自然數 n,證明

n = \sqrt{1 + (n - 1)\sqrt{1 + n\sqrt{1 + (n + 1)\sqrt{1 + (n + 2)\sqrt{1 + (n + 3)\dots}}}}}

Solution

Let P(n) be the proposition.

When n = 1, L.H.S. = 1 = R.H.S.
Hence P(1) is true.

Suppose P(k) is true, that is

k = \sqrt{1 + (k - 1)\sqrt{1 + k\sqrt{1 + (k + 1)\sqrt{1 + (k + 2)\sqrt{1 + (k + 3)\dots}}}}}

squaring both sides, yield

k^2 = 1 + (k - 1)\sqrt{1 + k\sqrt{1 + (k + 1)\sqrt{1 + (k + 2)\sqrt{1 + (k + 3)\dots}}}}
\frac{k^2 - 1}{k - 1} = \sqrt{1 + k\sqrt{1 + (k + 1)\sqrt{1 + (k + 2)\sqrt{1 + (k + 3)\dots}}}}
\therefore k + 1 = \sqrt{1 + k\sqrt{1 + (k + 1)\sqrt{1 + (k + 2)\sqrt{1 + (k + 3)\dots}}}}

Hence P(k + 1) is also true, by the principle of M.I., P(n) is true for all natural numbers n.

請問上述證明的錯誤在哪裡?

4 則迴響 »

  1. 係唔係LAST TWO STEP 除了K-1, ASSUME 了 K!=1, CONTRADICT 了 P(1) IS TRUE?
    請指教

    迴響 由 Ringo — 2008/07/19 @ 12:13 上午 | 回覆

  2. k-1應該要non-zero
    會唔會要先由P(1)推出P(2),再assume P(k) is true
    這樣可避免k-1=0的情況。
    過左AL咁耐,依家都唔係好識計數..-_-

    最近看了一個有關Fermat number的介紹: http://en.wikipedia.org/wiki/Fermat_number
    看來部分的recurrance relation可以出到一些pure math or add math的MI或者pure的lq,不過我仲未睇晒…內容都幾有趣,Fermat太神,只是一條Fermat’s last theorem就搞左d人幾百年..。

    迴響 由 Justin — 2008/07/19 @ 12:32 上午 | 回覆

  3. 應該把題目分成兩個case,當n=1為1個
    n>1的natural number為第2個

    迴響 由 Justin — 2008/07/19 @ 2:14 下午 | 回覆

  4. Note that, for a fixed natural number n, the R.H.S. is representing the limit (if it exists) of a sequence of numbers, say

    \sqrt{1 + (n - 1)}
    \sqrt{1 + (n - 1)\sqrt{1 + n}}
    \sqrt{1 + (n - 1)\sqrt{1 + n\sqrt{1 + (n + 1)}}}
    \dots

    The original question is actually asking the proof of the limit of the sequence above exists and the limiting value is n.

    As Ringo and Justin said, the so-called proof by M.I. is invalid, because the induction step from P(1) to P(2) fails since \frac{k^2 - 1}{k - 1} = k + 1 holds iff k \ne 1. However, we still cannot prove the validity of the proposition merely by means of M.I. even we divide cases like n = 1 and n > 1 as further comment by Justin. We may think that P(2) \Rightarrow P(3), P(3) \Rightarrow P(4), etc., yes, however, how to prove the validity of P(2)? That is, could you show that

    2 = \sqrt{1 + \sqrt{1 + 2\sqrt{1 + 3\sqrt{1 + 4\dots}}}}

    Well, it is of course provable. Just think a bit and I’ll write something about that later.

    The purpose of posting this is a reminder that we should be careful in using M.I., especially we need to look into the validity of the induction step. Ask: should we need extra condition(s) to ensure the validity of “P(k) \Rightarrow P(k + 1)" (say)?

    迴響 由 johnmayhk — 2008/07/19 @ 5:11 下午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: