[中學] 強歸納法

[Arton0306 (Ar藤)]

題目
Let C(N,K) = 1 for K = 0 or K = N,
and C(N,K) = C(N-1,K) + C(N-1,K-1) for N >= 1

Prove that C(N,K) = N! / K!(N-K)! for N >= 1 and 0<=K<=N.

想了一陣子 我用數學歸納法來證
A、Base Case:
C(N,0) = 1
N! / 0!(N-0)! = 1

C(N,K) = N! / K!(N-K)! for N>=1, K=0

B、Inductive Hypothesis:
假設 N<=n, K<=k 且 k < n 時，公式成立，即
C(n,k) = n! / k!(n-k)!
則
C(n,k+1) = C(n-1,k+1) + C(n-1,k)
         = (n-1)!/(k+1)!(n-k-2)! + (n-1)!/k!(n-1-k)!
         = [(n-1)!(n-k-1)+(n-1)!(k+1)]/(k+1)!(n-k-1)!
         = n! / (k+1)!(n-k-1)!
公式成立
得證
-----------------

結合A和B
C(N,0) C(N,1) ... C(N,K)都成立

但是我在B裡面用了很強的假設
"假設 N<=n, K<=k 且 k < n 時，公式成立"
從C(N,0)在A已證 利用B得到C(N,1)也成立 好像沒問題
但如果我直接把B的過程展開 C(N,1)=C(N-1,1)+C(N-1,0)
C(N-1,0)在A已證公式成立
C(N-1,1)的公式成立卻是假設的

我想問的是這樣的證明是否有問題呢?
以前學歸納法的時候，我會想著把Base case的值代入inductive的部份
例如在證f(n)=1^2+2^2+...+n^2=n(n+1)(2n+1)/6的時候
f(2)的展開只要用到base case的f(1)就好 所以很好理解
但上面的證明就不是了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.137.23.134
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1411487512.A.912.html
推 LPH66       : 你還需要另一個 base case C(N,N)
→ LPH66       : 這樣 C(2,1) 就能從 C(1,0) 跟 C(1,1) 導出來了
→ Arton0306   : 但C(N,N)題目有寫了，雖然我覺得題目雙重定義怪怪的
→ Arton0306   : 比較困擾的是這個證明架構 用了很強的假設
推 LPH66       : 關於你這個問題, 數學歸納法有所謂的「強形式」
→ LPH66       : 一般的歸納法是「P(n-1)→P(n)」
→ LPH66       : 強形式是「P(0)且P(1)且...且P(n-1)→P(n)」
→ LPH66       : 只要確定到你時前面的真的都成立那就行了
→ LPH66       : 其他都是一樣的
推 LPH66       : 事實上, 適當改寫問題即可將強形式轉為一般形式:
→ LPH66       : 令 Q(n) 為「P(0)且P(1)且...且P(n)」
→ LPH66       : 那強形式的推導就能寫成「Q(n-1)→Q(n)」
→ LPH66       : 以你的例子來說, (B)部份的結論可以再多走一步
→ LPH66       : 把前提跟結論合起來就能得到下一次的前提了
→ LPH66       : 這即是我上面寫的 Q(n)
→ Arton0306   : L大可以回文嗎XD 看不是很懂 要怎麼證才會都用到前
→ Arton0306   : 面已經確定成立的
我覺得原本證得太爛@@ 再重寫一次

---------------------------------------------
Base Case:
C(n,0) = 1 for n>=2
n! / 0!(n-0)! = 1 for n>=2

得
C(N,K) = N! / K!(N-K)! for N>=2, K=0
---------------------------------------------
Inductive Hypothesis:
假設
C(N,K) = N! / K!(N-K)! for N >= 1 and 0<=K<=N 在 K <= k 時都成立
則
C(n,k+1) = C(n-1,k+1) + C(n-1,k) 在 n>=2, n>k, k>=0 時成立
         = (n-1)!/(k+1)!(n-k-2)! + (n-1)!/k!(n-1-k)!
         = [(n-1)!(n-k-1)+(n-1)!(k+1)]/(k+1)!(n-k-1)!
         = n! / (k+1)!(n-k-1)!

因而得到
C(N,K)=N!/K!(N-K)! => C(N,K+1)=N!/(K+1)!(N-K-1)!
在 N>=2, N>K, K>=0 時成立
---------------------------------------------
由Base Case+inductive part可得
C(N,K)=N!/K!(N-K)! 在 for N >= 2 and 0<=K<N 都成立

C(N,N)=1=N!/N!0!
可得
C(N,K)=N!/K!(N-K)! 在 for N >= 2 and 0<=K<=N 都成立

C(1,0)=1=1!/0!1!
C(1,1)=1=1!/1!0!
可得
C(N,K)=N!/K!(N-K)! 在 for N >= 1 and 0<=K<=N 都成立

證畢
※ 編輯: Arton0306 (220.137.23.134), 09/25/2014 22:29:20
→ Arton0306   : 重證一次 原本證的漏洞太多
※ 編輯: Arton0306 (220.137.23.134), 09/25/2014 22:40:28
※ 編輯: Arton0306 (220.137.23.134), 09/25/2014 22:44:46