Research Space for Linear Algebra & Discrete Mathematics
欲證當n>=0時K(n)>=n，改證若n>=0時K(n)>=n+1>n。遞迴證明：n=0: K(0)=1>=1=0+1n=1: K(1)=K(0+1)=1+min(2K(floor(0/2)),3K(floor(0/3)))=1+min(2,3)=3>=2=1+1假設在n小於等於i時K(n)>=n+1均成立，則：K(floor(i/2))>=floor(i/2)+1=(i+2)/2或(i+1)/2=>2K(floor(i/2))>=i+1K(floor(i/3))>=floor(i/3)+1=(i+3)/3或(i+2)/3或(i+1)/3=>3K(floor(i/3))>=i+1因此，K(i+1)=1+min(2K(floor(i/2)),3K(floor(i/3)))=1+min(i+1,i+1)=i+2>=i+1得證
未看先謝~~~待我好好拜讀一番
懂了~~感恩~~~~
不好意思，應該是「歸納證明」，不是「遞迴證明」，我寫錯了 :p
張貼留言
4 則留言:
欲證當n>=0時K(n)>=n，改證若n>=0時K(n)>=n+1>n。
遞迴證明：
n=0:
K(0)=1>=1=0+1
n=1:
K(1)=K(0+1)
=1+min(2K(floor(0/2)),3K(floor(0/3)))
=1+min(2,3)
=3>=2=1+1
假設在n小於等於i時K(n)>=n+1均成立，則：
K(floor(i/2))>=floor(i/2)+1=(i+2)/2或(i+1)/2
=>2K(floor(i/2))>=i+1
K(floor(i/3))>=floor(i/3)+1=(i+3)/3或(i+2)/3或(i+1)/3
=>3K(floor(i/3))>=i+1
因此，K(i+1)
=1+min(2K(floor(i/2)),3K(floor(i/3)))
=1+min(i+1,i+1)
=i+2>=i+1得證
未看先謝~~~
待我好好拜讀一番
懂了~~感恩~~~~
不好意思，應該是「歸納證明」，不是「遞迴證明」，我寫錯了 :p
張貼留言