[中學] 強歸納法

看板Math作者 (Ar藤)時間9年前 (2014/09/23 23:51), 9年前編輯推噓3(3推 0噓 15→)
留言18則, 2人參與, 最新討論串1/3 (看更多)
題目 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
推
09/23 23:54, , 1F
你還需要另一個 base case C(N,N)
09/23 23:54, 1F
→
09/23 23:54, , 2F
這樣 C(2,1) 就能從 C(1,0) 跟 C(1,1) 導出來了
09/23 23:54, 2F
→
09/24 00:46, , 3F
但C(N,N)題目有寫了，雖然我覺得題目雙重定義怪怪的
09/24 00:46, 3F
→
09/24 00:49, , 4F
比較困擾的是這個證明架構 用了很強的假設
09/24 00:49, 4F
推
09/24 02:39, , 5F
關於你這個問題, 數學歸納法有所謂的「強形式」
09/24 02:39, 5F
→
09/24 02:40, , 6F
一般的歸納法是「P(n-1)→P(n)」
09/24 02:40, 6F
→
09/24 02:40, , 7F
強形式是「P(0)且P(1)且...且P(n-1)→P(n)」
09/24 02:40, 7F
→
09/24 02:40, , 8F
只要確定到你時前面的真的都成立那就行了
09/24 02:40, 8F
→
09/24 02:41, , 9F
其他都是一樣的
09/24 02:41, 9F
推
09/24 02:58, , 10F
事實上, 適當改寫問題即可將強形式轉為一般形式:
09/24 02:58, 10F
→
09/24 02:58, , 11F
令 Q(n) 為「P(0)且P(1)且...且P(n)」
09/24 02:58, 11F
→
09/24 02:59, , 12F
那強形式的推導就能寫成「Q(n-1)→Q(n)」
09/24 02:59, 12F
→
09/24 03:00, , 13F
以你的例子來說, (B)部份的結論可以再多走一步
09/24 03:00, 13F
→
09/24 03:00, , 14F
把前提跟結論合起來就能得到下一次的前提了
09/24 03:00, 14F
→
09/24 03:01, , 15F
這即是我上面寫的 Q(n)
09/24 03:01, 15F
→
09/24 13:56, , 16F
L大可以回文嗎XD 看不是很懂 要怎麼證才會都用到前
09/24 13:56, 16F
→
09/24 13:56, , 17F
面已經確定成立的
09/24 13:56, 17F
我覺得原本證得太爛@@ 再重寫一次 --------------------------------------------- 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
→
09/25 22:31, , 18F
重證一次 原本證的漏洞太多
09/25 22:31, 18F
※ 編輯: Arton0306 (220.137.23.134), 09/25/2014 22:40:28 ※ 編輯: Arton0306 (220.137.23.134), 09/25/2014 22:44:46
‣ 更多 Arton0306 的文章
文章代碼(AID): #1K8PSOaI (Math)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共3篇)
‣ 更多 Arton0306 的文章
文章代碼(AID): #1K8PSOaI (Math)