# Quod Erat Demonstrandum

## 2008/10/15

### 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

[Starting]
[Assuming]
[Proving]
[Conclusion]

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,…"

Actually,

“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

Advertisements

## 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 上午 | 回應