# Quod Erat Demonstrandum

## 2008/07/18

### 錯在哪裡之數學歸納法

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

$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 下午 | 回應