[tex]G(0)=1,G(1)=2,G(2)=4, G(n)=G(n-1) 2G(n-2) G(n-3)[/tex]
برای[tex]n\geq 3[/tex] کدام گزینه زیر بهترین جواب این رابطه است؟
جواب::[tex]g(n)\leq 4^{n}[/tex]
گزینه دیگه:[tex]g(n)\leq 2^{n 1}[/tex]
اینکه چرا[tex]g(n)\leq 4^{n}[/tex] متوجه میشم اما [tex]g(n)\leq 2^{n 1}[/tex] این نمیشه ،رو نمیتونم ثابت کنم
اونو باید جاگذاری کنی (یا کلا بری سوال بعد!) ، واسه بزرگتر مساوی ۱۲ دیگه اون رابطه برقرار نیست.
g(0)=1 < 2
g(1)=2 < 4
g(2)=4 < 8
g(3)=9 < 16
g(4)=19 < 32
g(5)=41 < 64
g(6)=88 < 128
g(7)=189 < 256
g(8)=406 < 512
g(9)=872 < 1024
g(10)=1873 < 2048
g(11)=4023 < 4096
g(12)=8641 > 8192
.
.
.
یعنی هیچ را ه دیگه ای نداره؟