Re: [理工] [離散]-數學歸納
※ 引述《gn00618777 (123)》之銘言：
: 證明full rooted binary tree 滿足 n=2i+1
: 歸納基底: i=0，n=1，只有root-->成立
: 歸納假設: 假設 i=k --> n=2k+1 成立
: 歸納推演: 則 i=k+1 --> n'= n+2，上述n=2k+1代入
^^^^^^^^^^^^^^^^^
這裡不夠嚴謹
: 得 n'=(2k+1)+2 =2(k+1)+1 得證!
: 請問我這樣證可以嗎？
使用數學歸納法，對某個整數變數做歸納時
通常這個整數值僅對應一個結果
而此題internal node數為i=k時卻有可能是很多種不同長相的樹
就算你的歸納假設是對所有擁有k個internal node二元樹都滿足命題
也不能直接說i+=1時node會+=2
也許你會想，事實就是這樣沒錯，每一個i=k+1的樹
都是由"某"個i=k的樹多加兩個external node而成
但是一個i=k的樹可以變成很多種i=k+1的樹
(相對一個i=k+1的樹，可以來自於很多不同i=k的樹擴增而成)
這中間不確定性太大了
就算你真的想這樣證，你至少要說明一下
為什麼可以保證每個i=k+1的樹都可以被推得
不然的話閱卷者憑什麼要從 i=k+1 --> n'= n+2 這樣一行
在心裡替你做以上討論，然後給你分數咧?
不過我還是覺得並不保險，畢竟教授要怎麼改誰都不知道
建議還是用左右子樹屬於歸納假設範圍，然後得出合併的大樹也會成立比較穩當
原因一樣
因為當你左右兩子樹決定之後(就是符合假設條件就好)，合併的二元樹是唯一的
這是兩種證明法嚴謹度不同的關鍵
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.25.160
※ 編輯: monkeykej 來自: 140.112.25.160 (03/23 19:51)
推
03/23 20:05, , 1F
03/23 20:05, 1F
推
03/23 22:12, , 2F
03/23 22:12, 2F
→
03/23 22:20, , 3F
03/23 22:20, 3F
討論串 (同標題文章)