Quod Erat Demonstrandum


Assuming step in mathematical induction

Just share a minor point in the presentation of M.I.

To prove that a proposition P(n) is true for all positive integers n by using M.I.

We need ‘4’ steps, namely


Just want to say something about [Assuming].

The textbook gives a good presentation like

“For any positive integer k, assume that P(k) is true,…"


“For any positive integer k" is NOT describing “assume that P(k) is true".

“For any positive integer k" is describing the fact that

“assume that P(k) is true, then P(k + 1) is also true".

or I prefer writing

“if P(k) is true, then P(k + 1) is true".

In symbol,

\forall k \in \mathbb{N}, (P(k) \Longrightarrow P(k + 1))

Urm, this is the principle of M.I..

Students always puzzled that why we CAN assume P(k) is true?

But actually, we are NOT merely “assume P(k) is true", but we are checking whether “P(k) \longrightarrow P(k + 1)" is true or not.

(Note that I used \longrightarrow instead of \Longrightarrow here.)

It is good to mention “For any positive integer k", because we actually need to describe clearly that what k is, as well as, we need to ensure, “For any positive integer k, (P(k) \Longrightarrow P(k + 1))“. Hence, it is actually not very good in writing something like

“Assume P(k) is true for some positive integer k, …"

P(k) is true for some k? The principle of M.I. may not be applicable.

Of course, it is WRONG to write

“Assume P(k) is true for any positive integer k."

Because, in this case, “for any positive integer k" is really describing the fact that “P(k) is true", and nothing we need to prove at all.

But, to avoid making confusion, I require student to write

“Assume P(k) is true."

Urm, this is NOT a clear expression. k is not defined clearly. But, at least, it is a ‘safe’ way of presentation in the public examination.

Also read
1. 「數學歸納法」還是「數學演繹法」? (written by Mr. Leung)
2. http://www.hkedcity.net/ihouse_tools/forum/read.phtml?forum_id=27877&current_page=&i=927029&t=926996&v=t


3 則迴響 »

  1. In my understanding,
    “Assume P(k) is true for some positive integer k, …”

    means P(k) is true and k in N.

    迴響 由 路過 — 2008/10/15 @ 10:25 下午 | 回應

  2. The statement

    “P(k) is true and k in N"

    is not very precise.

    The meaning may be one of the following

    \forall k \in \mathbb{N}  (P(k) \Longrightarrow P(k + 1)) – – – (1)
    \exists k \in \mathbb{N}  (P(k) \Longrightarrow P(k + 1)) – – – (2)

    The so-called principle of M.I. is something about (1).

    However, the statement

    “assume P(k) is true for some positive integer k"

    seems to state (2).


    在 induction step,

    我們不是亦不能「無端端」假設 P(k) 是真。

    我們不能假設對某個 P(k) 是真。

    P(100) 係咪真呢?



    無論 k 是什麼正整數(即,對任意一個正整數 k)<——- 就是 (1) 的 \forall k \in \mathbb{N}

    【一旦 P(k) 是真的話,P(k + 1) 就一定是真。】

    但 P(k) 是不是真?我們不關心。


    “assume P(k) is true for some positive integer k"

    即對某個正整數 k,假設 P(k) 是真。


    對某某正整數,比如 100,假設 P(100) 是真。

    做一做數,我們證實到 P(101) 也是真。

    但嚴格來說,我們得不到 “P(n) is true for ALL positive integer n." 這個結論。


    對任意一個正整數 k (for any positive integer k)【一旦 P(k) 是真的話,P(k + 1) 就一定是真。】

    再加上知道 P(1) 是真的話,我們才可得出

    “P(n) is true for ALL positive integers n." 這個結論。

    迴響 由 johnmayhk — 2008/10/16 @ 11:28 上午 | 回應

  3. 謝謝你的指點. 來到這裡, 才發現自己一直寫的東西都有這個毛病. 我還把這種錯的寫法教給我的(補習)學生.

    那麼, 如果為了清楚界定k是甚麼… 寫成這樣如何?
    (設問何必要界定得這麼清楚呢? 答曰induction step的步驟中或需正整數的性質云云.)

    (a) Let k be a positive integer. Assume P(k) is true, …
    (b) Whenever P(k) is true. If $\latex k$ is a positive integer, …

    (如果無須正整數性質, 乾脆刪掉(a)的首句或(b)的末句.)

    可以不寫 “is true", 直接把 P(k) 當作謂詞?

    (為甚麼習慣用 k 呢. 我總是覺得 P(k) 這個讀法很好笑. “如果P(k)嘅話,…/ 每當P(k)時,…")

    迴響 由 chin — 2012/05/14 @ 12:35 上午 | 回應

RSS feed for comments on this post. TrackBack URI



WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )


您的留言將使用 Facebook 帳號。 登出 /  變更 )


連結到 %s


%d 位部落客按了讚: