¡Dì¸ü©ó¼Æ¾Ç¶Ç¼½²Ä¤G¨÷²Ä¥|´Á ¡D§@ªÌ·í®É¥ô±Ð©ó²MµØ¤j¾Ç¼Æ¾Ç¨t | |||
¥Í¦¨¨ç¼Æ»P®t¤À¤èµ{
®L©v¶× |
²Õ¦X¼Æ¾Ç¬O¤@ªù¦³¼sªxÀ³¥Î¥B»á¤Þ¤H¤J³Óªº¼Æ¾Ç¤ÀªK¡C¬ãŪ²Õ¦X¼Æ¾Ç¨Ã¤£»Ýn¤Ó¦h¼Æ¾ÇI´º;¦b°ª¤¤¼Æ¾ÇùØ«K¤w¤¶²Ð¤F³\¦h¦³½ì¥B§xÃøªº±Æ¦C²Õ¦X°ÝÃD¡C¦ý¦b¨ºùةҥΪº¤èªk«o¬Oªìµ¥ªº¡F¦³¦p¸Ñºâ³NÃD¡A¨C¤@°ÝÃD¦³¦U¦Û«ä¦Ò¤èªk»P§Þ¥©¡C¦b¥»¤å¤¤§Ú̱N°Q½×¤@Ãþ±Æ¦C²Õ¦X°ÝÃD¡A¥¦Ì¥i¥H¥Î¦C½u©Ê¦^Âk¤èµ{ (linear recurrence) ªº¤èªk¨Ó¨D¸Ñ¡A¨Ã¥Î¨ÒÃD¨Ó»¡©ú¨âºØ¦^Âk¤èµ{¨D¸Ñªº¨BÆJ¡C§ÚÌ©Ò§@¶È¬°¤@²Ê²L¤¶²Ð¡A©Ò¿ï¨úªº§÷®Æ¥i¬°Åª¹L·L¿n¤ÀªºÅªªÌ©Ò±µ¨ü¡C¦³¿³½ìªºÅªªÌÀ³¶i¤@¨B°Ñ¾\¥»¤å«á©Ò¦C°Ñ¦Ò¸ê®Æ¡C
§ÚÌ¥ý¥Î¨ÒÃD¨Ó»¡©ú¦^Âk¤èµ{ªº¼Æ¾Ç·N¸q©M¥¦»P±Æ¦C²Õ¦X°ÝÃD¤§Ãö«Y¡C
[¨Ò1]
³]¦³ n Ó¥b®|»¼¼Wªº¶êÀô¨Ì¤j¤p®M¦b¤@¶ê¬W¤W¡A³Ì¤jªºÀô¦b³Ì¤U±¡C§ÚÌn±N³o¨ÇÀô²¾¸m¦Ü¥t¤@¶ê¬W¤W¡A¥t¦³²Ä¤TÓ¶ê¬W§@¼È®É©ñ¸m¶êÀô¥Î¡A¦ý²¾¸m®É³W©w¤jÀô¥Ã¤£¥i©ñ¦b¤pÀô¤W±¡A¨C¦¸²¾°Ê¤@ÓÀô¡A°Ý³Ì¤Ön²¾°Ê´X¦¸¤~¥i±N n ÓÀô¥Ñ¤@¶ê¬W²¾¦Ü¥t¤@¶ê¬W¡H³o«K¬OµÛ¦Wªº¡uªe¤º¤§¶ð¡v°ÝÃD (The tower of Hanoi problem)¡CÅ㨣·í n=1 ®É¡A§ÚÌ¥u»Ý 1¨B¡F·í n=2 ®É¡A§ÚÌ»Ýn 3 ¨B¡C¦ý·í n «Ü¤j®É¡A¨Ò¦p¡A n=64¡A°ÝÃDªºµª®×«K¤£ÅãµM¤F¡C³] an (n=1,2,3,¡K) ¬°²¾°Ê n ÓÀôªº³Ì¤Ö¦¸¼Æ¡A«h a1=1, a2=3¡C¦pªG n>2¡A§ÚÌ¥i¥ý¥Î an-1 ¨B±N²Ä¤@¬W¤W±¤§ n-1 ÓÀô²¾¦Ü²Ä¤T¬W¤W¡AµM«á±N³Ì¤jÀô²¾¦Ü²Ä¤G¬W¡A³Ì«á¦A¥Î an-1 ¨B±N²Ä¤T¬W¤W¤§ n-1 ÓÀô©ñ¦b²Ä¤G¬W³Ì¤jÀô¤§¤W±¡C³o¼Ë«K§¹¦¨¥H³Ì¤Ö¨B¼Æ²¾¸m³o n ÓÀô¡A¬G±o
¼Æ¦C ![]()
§ÚÌ¥ý´£¥X¥Í¦¨¨ç¼Æªº©w¸q¡C³]
![]() ºÙ¬°»P¼Æ¦C ![]() ![]() ¬O»P¼Æ¦C ![]() ![]() ¨ä¤¤ ![]() ¥Í¦¨¨ç¼Æ f(x) ¤§¾É¼Æ¬O ![]() ¥»¤å©Ò¦Ò¼{ªº¥Í¦¨¨ç¼Æ§¡¬°¾ã«Y¼Æ¡C¦pªG¥Ñ(3)µ¹¥X¤§¥Í¦¨¨ç¼Æ f(x) ¬O¾ã«Y¼Æªº¥Bº¶µ«Y¼Æ a0 ¬° 1¡A«h f(x) ÁÙ¥i¥H°£¥t¤@¾ã«Y¼Æªº¥Í¦¨¨ç¼Æ¡A©Ò±o¤§°Ó¤´¬°¤@¾ã«Y¼Æ¥Í¦¨¨ç¼Æ¡C¨âӥͦ¨¨ç¼Æ¬Ûµ¥¶È·í¥¦Ì¹ïÀ³¤§«Y¼Æ§¡¬Ûµ¥¡C§Ú̱N¦b¨ÒÃD¤¤¥Î¹ê»Úpºâ¨Ó»¡©ú³o¨Ç¹Bºâ¡A¤£¦A¦b²z½×¤W§@¸Ô²Ó»¡©ú¡A¨ä²z½×°ò¦½Ð°Ñ¾\°Ñ¦Ò¸ê®Æ[3]¡C¦³Ãö¥Í¦¨¨ç¼Æ¦b²Õ¦X¼Æ¾Ç¤¤¤§¨ä¥¦À³¥Î¥i°Ñ¾\[2,4]¡C
¦^¨ì¦^Âk¤èµ{(1)¡AÅ㨣¥i¥O a0=0¦Ó¤´«O«ù¥Ñ¦¡(1)¤Î(2)©Ò«Ø¥ß¤§Ãö«Y¡C±Nº¡¨¬(1)»P (2)¤§¦U¼Æ¥Î¼Æ¦C
![]() ¦p±N¤W±¤Tӥͦ¨¨ç¼Æ¬Û¥[¡A«h¥Ñ¦¡(1)¤Î a0 ¤§©w¸q¥iª¾©Ò±o¤§¥Í¦¨¨ç¼Æªº«Y¼Æ¥Ñ²Ä¤G¶µ°_§¡¬°¹s¡Fg(x) ¤U±ªº¤G¥Í¦¨¨ç¼Æ«K¬O¨Ì¾Ú¦¹¤@ì«h©Ò©w¥X¡C¬G±o ![]() ¸Ñ¥X g(x) ¦³ ![]() ¦]±oº¡¨¬Ãä¬É±ø¥ó(2)¤§¤èµ{(1)ªº¸Ñ¬° ![]() ·í n=64 ®É¡A²¾°Ê 64 ÓÀôªº³Ì¤p¨B¼Æ an=264-1 ¬Oӫܤj¼Æ¦r¡C
[¨Ò2] ¦b¥±¤Wµe n Ó¾ò¶ê¡A¨C¨âÓ¥²«ê¦n¥æ©ó¨âÂI¡A¦ý¨C¤TÓ¤S¤£¯à¥æ©ó¦P¤@ÂI¡A°Ý³o¨Ç¾ò¶ê±N¥±¤À¹j¦¨¦h¤Ö°Ï°ì?
³] an (n=1¡A2¡A¡K)¬° n Ó¾ò¶ê±N¥±¤À¹j¤§°Ï°ìӼơA«hÅ㨣 a1=2, a2=4¡C·í ![]() ©w¸q a0=2 ¨Ã³] g(x) ¬°¼Æ¦C ![]() ![]() ¨ä¤¤¡A¤W±²Ä¤TÓµ¥¦¡¥i¥Ñ¤Uªk¾É¥X: ![]() ±N¤W¤T¦¡¬Û¥[±o ![]() §Y ![]() ¦]¬° ![]() ¬G ![]() ³Ì«á±o¦^Âk¤èµ{(4)¤§¸Ñ¬° ![]() [¨Ò 3] °Ý¦b¥Î¾ã¼Æ 0 »P 1 ²Õ¦¨ªº n ¦ì¼Æ¤¤¡A¦³¦h¤Ö¤£§t¨âÓ¬Û³sªº 0?
Å㨣¦³ 2 Ó¤@¦ì¼Æ¡F3 Ó¤G¦ì¼Æ¡G01,10 »P 11¡C³] an ¬°¥Ñ 0 »P 1 ©Ò²Õ¦¨¤£§t¨âÓ¬Û³sªº 0 ¤§ n-1 ¦ì¼Æ¤§Ó¼Æ¡]¨ä¤¤ n ¿ù¶}¤@¦ì¬O¥Ñ©ó¾ú¥v¤Wì¦]¡^¡A«h±o¦^Âk¤èµ{
![]() ³o¬O¦]¬°¦b¤£§t¨âÓ¬Û³sªº¹s¤§¥Ñ 0 »P 1 ²Õ¦¨ n-1 ¦ì¼Æ¤¤¡A³Ì«á¤@¦ì¼Æ¦p¬O¹s¡A«h³Ì«á²Ä¤G¦ì¼Æ´N¤£¯à¬O¹s¡A³o¼Ëªº¼Æ¤@¦@¦³ an-2 Ó¡F³Ì«á¤@¦ì¼Æ¦p¬O 1¡A«h«e± n-2 Ӽƥi¥ô·N¿ï¨ú 0 ©Î 1¡A¥un¨âÓ¹s¤£¬Û³s«K¥i¡A³o¼Ëªº¼Æ¤@¦@¦³ an-1 Ó¡C¦¡(5)µ¹¥X¤TÓ¬Û³sªº an ¤§ÈÃö«Y¡AºÙ¬° 2 ¶¥¦^Âk¤èµ{¡A»Ýn 2 ÓÃä¬É±ø¥ó¡C¥Ñ(5)§ÚÌ¥i©w¸q a1=1, a0=1¡C¨Ì«eªk¡A¥O g(x) ¬O¼Æ¦C ![]() ![]() ¬G±o
g(x)(1-x-x2) = 1
§Q¥Î³¡¤À¤À¦¡±o ![]() ¨ä¤¤ ![]() ¬G±o¦^Âk¤èµ{(5)¤§¸Ñ¬O ![]() ¹ê»Ú¤W¼Æ¦C ![]() ![]() ³o¨Ç¼ÆºÙ¬° Fibonacci¼Æ¡A¥¦ÌI«áÂ泤@¬q¾ú¥v±y¤[¥B»á¨ã½ì¨ýªº¼Æ¾Ç¬G¨Æ¡C¦ý³o¨Ç¤w¤£¦b¥»¤å½d³ò¤º¤F¡C
«e±§ÚÌ´£¥X¤F´XÓ²³æªº¦^Âk¤èµ{ªº¨Ò¤l¡A¨Ã»¡©ú¥Î¥Í¦¨¨ç¼Æ¨D¸Ñªº¹Lµ{¡C¦b¤U±§Ú̱N¦^Âk¤èµ{¬Ý¦¨¬O¤@ºØ®t¤À¤èµ{¡A¨Ã¤¶²Ð¥t¤@ºØ¤èµ{¨D¸Ñªº¤èªk¡C§Ṳ́w´£¹L¤@ӼƦC a=
![]() °ª¶¥®t¤Àºâ¤l ![]() ![]() §Ų́éw¸q ![]()
Ean=an+1
°ª¶¥¦ì²¾ºâ¤l Ek (k=2,3,¡K) ¬O©w¸q¬°
Ekan=E(Ek-1an)=an+k
§Ų́éw¸q E0=I¡AÅ㨣¦³ ![]() ![]() ¨ä¤¤ ![]() ![]() «ez¤§¤èµ{ (1)»P (4)§¡¬O¤@¶¥«D»ô¦¸®t¤À¤èµ{;¤èµ{ (5)¬O¤G¶¥»ô¦¸®t¤À¤èµ{¡C§Q¥Î¦ì²¾ºâ¤l¡A¤èµ{ (6)»P (7)¤S¥i°O¬° ![]() ¤Î ![]() ¤èµ{ (9)¤§¸ÑºÙ¬°»ô¦¸¸Ñ¡F¥ô·Nº¡¨¬¤èµ{ (8) ¤§¸ÑºÙ¯S§O¸Ñ¡CŪªÌ¤w¥iÆ[¹î¨ì k¶¥±`«Y¼Æ½u©Ê®t¤À¤èµ{»P·L¿n¤À¤¤ªº k ¶¥±`«Y¼Æ½u©Ê·L¤À¤èµ{¤§¶¡¬Û¦ü©Ê¡F¹ê»Ú¤W¥¦Ì¤§¶¡¦³³\¦h¬Û¥¦æªº©Ê½è¡C¨Ò¦p©Ò¦³»ô¦¸¸Ñ§Î¦¨ªº¶°¦X¬O¤@¦V¶qªÅ¶¡¡F¤èµ{(8)¤§¸Ñ¥²¬°¤@Ó»ô¦¸¸Ñ¤Î¬YÓ¯S§O¸Ñ¤§©M¡C³o¨Ç©Ê½èªºÃÒ©ú»P·L¤À¤èµ{¤¤¬ÛÀ³©Ê½èªºÃÒ©ú¬Û¦ü¡A§Ṳ́£¦b¦¹¸Ô²Ó»¡©ú¡C¦³Ãö®t¤À¤èµ{¤@¯ë©Ê½è½Ð°Ñ¾\°Ñ¦Ò¸ê®Æ[1]¡C
¤U±§ÚÌ°Q½× k¶¥»ô¦¸±`«Y¼Æ½u©Ê®t¤À¤èµ{ (9)¤§¨D¸Ñ¨BÆJ¡C¦b (9)¤¤¥O an=rn¡A§Ú̦³
![]() §Ṳ́£¦Ò¼{ r=0ªº±¡ªp¡A¬G¤S¦³ ![]() ¤èµ{ (10)¬O¤@¦¸¥N¼Æ¤èµ{¦¡¡AºÙ¬°»P (9)¹ïÀ³¤§¯S¼x¤èµ{¦¡;¥¦¦³ kÓ®Ú¡AºÙ¬°¤èµ{ (9)¤§¯S¼x®Ú¡C¦pªG (10)¦³ kÓ¤£¦Pªº®Ú r1¡A r2¡A ¡K¡A rk¡A«h¥ô¤@¤èµ{ (9)¤§¸Ñ¦³§Î¦¡ ![]() ¨ä¤¤ A1, A2, ¡K, Ak ¬O¥¼©w«Y¼Æ¡A¥Ñ©Òµ¹¥XªºÃä¬É±ø¥ó©Ò¨M©w¡C¦pªG¤@¯S¼x®Ú r¬O (10)¤§ m «®Ú¡A«h»P¤§¹ïÀ³ªº»ô¦¸¸Ñ¬O ![]() ¦pªG¤èµ{ (10)¦³¤@¹ï¦@³m½Æ®Ú p+qi ¤Î p-qi¡A«h»P¤§¹ïÀ³¤§»ô¦¸¸Ñ¤S¥i¼g¦¨ ![]() ¨ä¤¤ ![]() ![]()
[¨Ò4]
![]() ¤èµ{ (11)¤§¯S¼x¤èµ{¬O
r2-r-1=0
¥¦¦³¨âÓ¤£¦Pªº¯S¼x®Ú ![]() ![]() ![]() ¬°¤F¨M©w¥¼©w«Y¼Æ A1 »P A2¡A§Ú̱N(11)¤¤¤§Ãä¬É±ø¥ó¥N¤J(12)±o ![]() ¸ÑÁp¥ß¤èµ{ (13)±o ![]() ¦]¦¹¤èµ{ (11)¤§¸Ñ¬O ![]()
[¨Ò5] pºâ n ¶¥¦æ¦C¦¡
![]() ³] (14)¤¤¤§ n¶¥¦æ¦C¦¡¤§È¬° an¡A¥Ñ²Ä¤@¦C±N (14)®i¶}±o®t¤À¤èµ{ ![]() ¥¦ªº¯S¼x¤èµ{¬O r2-r+1=0¡A¬G¦³¨âÓ¦@³m½Æ®Ú ![]() ![]() ±o¤èµ{ (15)¤§»ô¦¸¸Ñ¦³§Î¦¡ ![]() ±N (15)¤¤¤§Ãä¬É±ø¥ó¥N¤J (16)¦³ ![]() ±q¦Ó±o¥¼©w«Y¼Æ B1=1¡A ![]() ![]() ¥Ñ¤èµ{ (15)¥i¨£¥Ñ n=1°_ an¤§Èªºº´X¶µ¬O ![]() ³Ì«á§Ṳ́¶²Ð¤@ºØ«D»ô¦¸®t¤À¤èµ{ (8)ªº¨D¸Ñ¨BÆJ¡C¥Ñ¤W±°Q½×ª¾¥u»Ý¨D¥X¤èµ{ (8)ªº¬YÓ¯S§O¸Ñ¡C§Ú̩ҥΪº¬O¤@ºØ¸gÅçªk¡A¬O¥Ñ¤èµ{ (8)¤§¥kÃä bn¤§§Î¦¡¨Ó§PÂ_¯S§O¸Ñ¥i¯à¦³ªº§Î¦¡¡AµM«á¦A¨M©w¨ä¤¤¥¼©w«Y¼Æ¡C¤Uªí¦C¥X´XºØ±`¹J¨ìªº bn§Î¦¡ ![]() ¨ä¤¤ªí¤§¥k¦C¤¤ B,B1,B2,¡K,Bp ¬°¥¼©w«Y¼Æ¡C³oºØ¸Ñªk¤]¬O¨D±`·L¤À¤èµ{¤§«D»ô¦¸¸Ñ®É±`¥Î¤èªk¤§¤@¡AŪªÌÀ³¹ï³o¨âºØ±¡ªp¤§²§¦P§@¤@¤ñ¸û¡C
[¨Ò6] °Ý¦b¥Ñ 0,1,2,3 ©Ò²Õ¦¨ªº n ¦ì¼Æ¤¤¦³¦h¤Ö§t¦³°¸¼ÆÓ¹s¡H
³] an ¬O¥Ñ 0,1,2,3 ©Ò²Õ¦¨ªº n ¦ì¼Æ¤¤§t°¸¼ÆÓ 0 ªºÓ¼Æ¡A«h¦b³o¨Ç¼Æ¤¤¡A³Ì«á¤@¦ì¼Æ©ÎªÌ¤£¬°¹s¡A³o¼Ëªº¼Æ¦³ 3an-1 Ó¡F©ÎªÌ³Ì«á¤@¦ì¼Æ¬°¹s¡A«h¥¦«e± n-1¦ì¤¤¥²¦³©_¼ÆÓ¹s¡A³o¼Ëªº¼Æ¤@¦@¦³
4n-1-an-1 Ó¡A¬G±o
an=3an-1+4n-1-an-1¡CÅãµM¦³ a1=3¡A¬G©Ò¨Dªº®t¤À¤èµ{¥i¼g¦¨
![]() ¤èµ{ (18)¤§¯S¼x¤èµ{¦¡ r-2=0¡A¥¦¦³°ß¤@ªº¯S¼x®Ú r=2¡A¬G±o¤èµ{(18)¤§»ô¦¸¸Ñ¦³§Î¦¡
an=A2n
¨ä¤¤ A ¬O¥¼©w«Y¼Æ¡C¬°¤F¨D¤èµ{ªº¯S§O¸Ñ¡A¥Ñªí(17)±o¥¦¦³§Î¦¡ an=B4n¡A¨ä¤¤ B¬°¥¼©w«Y¼Æ¡C¥N¤J¤èµ{(18)±o
B4n+1-2B4n=4n
±q¦Ó ![]() ![]() ±N(18)¤¤Ãä¬É±ø¥ó¥N¤J(19)±o ![]() ![]() ¥Î¸ÕÅç¸Ñªk¨D¯S§O¸Ñ¤]¦³¥¢®Äªº±¡ªp¡A¨º®É§ÚÌ¥²»Ý§@¥²nªº×¥¿¡C³Ì«á§ÚÌÁ|¤U¨Ò¨Ó»¡©ú¦¹ÂI¡C
[¨Ò7]
¸Ñ®t¤À¤èµ{
![]() ¤èµ{ (20)ªº¯S¼x¤èµ{¬O r-1=0¡A¬G¥¦¦³°ß¤@ªº¯S¼x®Ú r=1¡C¦]¦¹¤èµ{(20)ªº»ô¦¸¸Ñ¬O an=A(1)n=A¡A¨ä¤¤ A ¬O¥¼©w«Y¼Æ¡C®Ú¾Úªí(17)¤èµ{(20)ªº¯S§O¸Ñ¦³§Î¦¡ ![]() ¦ý»ô¦¸¸Ñ»P¯S§O¸Ñ¤¤§¡¦³¤@¶µ¬O±`¼Æ¡A±N (21)¥N¤J (20)±NµLªk¨M©w¥¼©w«Y¼Æ B1¡C³o®É§ÚÌ¥i¥H±N¯S§O¸Ñ¼¤@³Ì§C¦¸¼Æ¤§ n ªº¾ã¼Æ¾¡A¨Ï±o»ô¦¸¸Ñ»P¯S§O¸Ñ¤¤ªº³oºØ¬Û¦ü¶µ®ø¥¢¡C¦]¦¹§ÚÌ¥i¥O¤èµ{(20)¤§¯S§O¸Ñ¦³§Î¦¡ an=B1n+B2n2 ¨Ã¥N¤J(20)±o
B1(n+1)+B2(n+1)2-B1n-B2n2 = 2n
¤ñ¸û¨âÃä«Y¼Æ±o B1=-1, B2=1¡C¤èµ{(20)¤§¥ô¤@¸Ñ§¡¦³§Î¦¡ ![]() ±N(20)¤¤¤§Ãä¬É±ø¥ó¥N¤J(21)±o A=2¡A¦]¦¹¤èµ{(20)¤§¸Ñ¬°
an=n2-n+2
|
¹ï¥~·j´MÃöÁä¦r¡G ¡D®t¤À¤èµ{ ¡D¥Í¦¨¨ç¼Æ ¡DFibonacci ¡D·L¤À¤èµ{ ¡D²Õ¦X¾Ç ¡D¶O¤ó¼Æ¦C |
|
![]() |
¡]Y¦³«ü¥¿¡BºÃ°Ý¡K¡K¡A¥i¥H¦b¦¹ ¯d¨¥ ©Î ¼g«H µ¹§ÚÌ¡C¡^ |
![]() |
EpisteMath (c) 2000 ¤¤¥¡¬ã¨s°|¼Æ¾Ç©Ò¡B¥x¤j¼Æ¾Ç¨t ¦Uºô¶¤å³¹¤º®e¤§µÛ§@Åv¬°ìµÛ§@¤H©Ò¦³ |
½s¿è¡G³¯¤å¬O | ³Ì«áקï¤é´Á¡G4/26/2002 |