[理工] [離散]-數學歸納

[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 得證!


請問我這樣證可以嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.138.106.129
→ chris750630:n啥 i啥阿...?
→ gn00618777:n是node個數,i是內點個數，噗成大榜單出來了
→ windysoul:所以該恭喜樓上還是？？  我備取5x.....
→ gn00618777:看來我真的要上成功嶺了
→ chris750630:拍拍.....
→ windysoul:拍拍
→ gn00618777:沒人回答我問題阿>"< ，我這樣可以嗎？
推 chris750630:我想了很久 感覺怪怪的... 但又說不出那兒怪
→ chris750630:可以敘述一下 位啥內點+1 node要+2嘛？
→ gn00618777:不管內點多在哪邊，都會增加兩個node @@
→ windysoul:內點叫做非葉節點  node就是所有的節點
推 chris750630:那討論歪斜數 中間那些點都是非葉節點嘛？
→ windysoul:阿阿 我說錯了  先忽略我的話
→ gn00618777:=.=?
推 chris750630:結.. 結論？
→ gn00618777:既然覺得怪怪的，那我只好照解答的證法囉@@
→ gn00618777:只是想證明自己不看解答也可以證出來= =..
推 kib65060:我覺得假設那邊不能寫K 要寫 n <= k
→ kib65060:我覺得要利用強數學歸納法證明
→ gn00618777:為什麼一定要用強數學歸納？跟一般有差嗎？