线性递归数列

维普资讯 http://www.cqvip.com 第２２卷第２期　２００２年６月　承德民族师专学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈｅｎｇｄｅ　Ｔｅａｃｈｅｒｓ　Ｃｏｌｌｅｇｅ　ｆｏｒ　Ｎａ　ｔｉｏｎａｌｉ　ｔｉｅｓ　Ｖｏ１．２２　Ｎｏ．２　Ｊｕｎ．２００２　线性递归数列　陈　军　（承德民族师专　数学系，　河北　承德０６７０００）　摘　要：讨论线性递归￣ｃ７，１的性质，由递推公式和特征方程解的情况得出通项公式。　关键词：线性组合；特征方程；通项　中图分类号：Ｏ１５１．２　文献标识码：Ａ　为叙述方便这里再描述线性递归数列之定义　定义１　若数列｛ａｎ｝满足下列条件　ｌ１＋ｋ—Ｐ１ａｎ１卜ｋ＿＿】＋Ｐ２ａ　＋ｋ一２＋…＋ｐｋａ　（１）　其中ｎ∈Ｎ，ｐ　，Ｐ　，…ｐｋ是常数且ｐｋ≠０则称　｛ａ　｝为ｋ阶线性递归数列．（１）叫｛ａ　｝的递归方程．　其特征方程为　ｘ　一ｐ１ｘ　一　＋ｐ２ｘ　一　＋…＋ｐｋ　（２）　一、线性递归数列的性质　性质１　满足同一线性递归方程（１）的线性递　归数列的线性组合亦是由（１）确定的线性递归数列。　证　设｛ｕ　｝，｛ｖ　｝，…｛ｗ　｝均是由（１）确定的ｋ　个线性递归数列．我们证明｛ｃ　ｕ　＋Ｃ２ｖ　＋…Ｃｋｗ　｝　也是满足（１）的数列。由于　ｕ　＋ｋ＝ｐｌＵｎ＋ｋ一１＿１一ｐ２ｕｎ＋ｋ一２＿１一…＿｛一ｐｋＵ　Ｖｎ＋ｋ＝ｐ１Ｖ　＋ｋ一１＋Ｐ２Ｖ　＋ｋ～２＋…＋ｐｋＶｎ　…　…　（３）　ｗ　＋ｋ—ｐ１ｗ　＋ｋ一１＋Ｐ２ｗ　＋ｋ一２＋…＋ｐＫＷ　以Ｃ　，Ｃ　，…Ｃ　分别乘以（３）的各式再相加，得　Ｃ１Ｕｎ＋ｋ＋Ｃ２ｖ　＋ｋ＋…＋ＣｋＷ　＋ｋ＝Ｃｌ［ｐ１　ａｎ＋ｋ一１＋　ｐ２ｕ　＋ｋ一２＋…＋ｐｋｕ　］　＋Ｃ２［ｐ１　Ｖｎ＋ｋ一１＋ｐ２ｖＩｌ＋ｋ＿＿２＋…＋ｐｋｖ　］　＋ｃｋＥｐｌ　ｗ　＋ｋ－＿ｌ＋ｐ２ｗ　＋ｋ一２＋…＋ｐｋｗ　］　＝＝：ｐｌ　ｃ１　Ｕｎ＋ｋ一１＋Ｃ２　ｖ。件ｋｎ＿ｌ＋…＋Ｃｋ　ｗ　十ｋ—１］＋　ｐ２Ｌｃ１　Ｕｎ＋ｋ一２＋Ｃ２　Ｖｎ＋ｋ一２＋…＋Ｃｋ　ｗ　＋ｋ一２］＋…　＋ｐｋ［ｃ１　Ｕｎ＋ｃ２ｖ　＋…＋ｃｋｗ　］　＝ｐｌ　ｂｎ＋ｋ—ｌ＋ｐ２　ｂｎ＋ｋ一２＋…＋ｐｋｂ　反之，若数列｛ｂｎ｝适合（１），那么　ｂ　＋ｋ—Ｐ１　ｂｎ＋ｋ一１＋ｐ２　ｂｎ＋ｋ一２＋…＋ｐｋ　ｂ　收稿日期：２００１—１１—１　９　作者简介：陈军（１　９６３～）男．回族。宁夏回族自治区石嘴　山市人．承德民族师专数学系讲师。　～１２一　文章编号：１００５—１５５４（２００２）０２－－００１２－－０２　只需令　ｂｌ　＋ｋ—ｌ＝Ｃｌ　Ｕｎ＋ｋｌ＋ｃ２　Ｖ『Ｉ＋ｋ．一ｌ＋…＋ｃｋ　Ｗｎ＋ｋ一１　ｂ　＋ｋ一２：　１　ｕ　＋ｋ一２＋ｃ　ｒＩ１＋ｋ　２＋…＋　ｋ　ｗ　＋ｋ　２（４）　ｂ　一ｃ１Ｕ　十Ｃ２ｖ　＋…＋Ｃｋｗ　一　而此关于Ｃ　Ｃ：…Ｃ一　　的方程组有唯一解的充要条　　一件是其系数行列式　也就是说（５）成立则总能找到唯一的Ｃ　Ｃ　……　Ｃｋ使得　ｂ　一ｃ１　ｕ　＋ｃ２ｖ　＋…＋Ｃｋｗ　成立　所以｛ｂ　｝是满足（１）的数列。　性质２若ｘ（ｘ≠０）适合特征方程（２）则｛ｘ“｝　是由（１）确定的数列。　证Ｘ适合特征方程（２）则有　ｘ　一ｐｌＸ　一　＋ｐ２ｘ　一　＋…＋ｐｋ　由于ｘ≠０上式两端同乘以ｘ“有　ｘｎ＋ｋ＝ｐｌｘｎ１卜　一　＋ｐ２ｘｎ１卜　一。＋…＋ｐｋｘ　即｛Ｘ　｝适合（１）　反过来，若｛ｘ“）适合（１）即得　ｘ　一Ｐｌｘ　一　＋ｐ２ｘ　一　＋…＋Ｐｋ　所以，ｘ≠０是（２）的解。　性质３若｛ａ　｝是由（１）确定的ｋ阶线性递归数　列，它的前ｎ项和为ｓ　，则｛ｓ　｝是ｋ＋１阶线性递归　数列，其递归方程为　Ｓｎ＋ｋ＋１一（１＋Ｐ１）Ｓｎ＋ｋ＋（ｐ２一Ｐ１）Ｓｎ＋ｋ—ｌ＋…　＋（ｐｋ—Ｐｋ—１）ｓ　＋ｌ—ＰｋＳ　维普资讯 http://www.cqvip.com 陈　军／著　证　Ｓｎ＋ｋ＋ｌ—ｓｌ１＋ｋ＋ａｎ＋ｋ＋１　一Ｓ　ｎ＋ｋ＋Ｅｐ１ａ¨ｋ＋ｐ２ａ　１＋ｋ＿．１＋…＋ｐｋａ　＋１］　一Ｓ　ｋ＋［ｐ｛（Ｓ【】＋ｋ—Ｓｌ１＋ｋ—１）＋Ｐ！（Ｓｎ＋ｋ一１一　Ｓ　ｋ　２）＋…＋ｐｋ（ｓ　１一ｓ　）Ｊ　一（１＋Ｐ１）ｓ：ｌ十ｋ＋（Ｐ！一Ｐ１）ｓ　ｋ一１＋…十（ｐｋ　ｐｋ　１）Ｓ　＋１一ｐｋｓ　二、线性递归数列之通项　１．数列｛ａ　｝满足（１）且其特征方程（２）无重根。　这时方程（２）即为（Ｘ一入１）（Ｘ一入２）…（Ｘ－－Ｘｋ）一　Ｏ（ｉ≠ｊ时Ｘｉ＝￣Ｘｊ）　构造以下ｋ个数列。　１，入ｌ，入　，…，入　。。，…　１，入！，入　，…，入：一，…　●●●　●●●　●●●　●●●　１，入ｋ，入　，…，入　～，…　由性质２知这个数列均满足递推公式（１），再由性质　１这ｋ个数列的线性组合构成的数列　ｂ　｝其中　ｂ　一ｃｌ入ｎ＿】＋ｃ２　。＋…＋ｃｋＸ￣。　是满足递推公式（１）的数列。而关于Ｃｉ（ｉ一１，　２，…ｋ）的方程组　Ｃｌ　十ｃ２　十…十　Ｃｋ　ｅｌ　ｃｌ入ｌ＋ｃｚＸ２十…＋Ｃｋ￣．ｋ—ａ２　ｃｌ入ｌ　一　＋ｃ：入２　＋…＋ｃｋ入ｋ　‘　一ａｋ　其系数行列式为范德蒙行列式　　’１　１　１　一　（　一入。）≠Ｏ　●●●　●●●　●●●　ｉ＜ｉ　故方程组有且只有一组解，故Ｃ　，Ｃ。，…Ｃ　唯一　确定。　这样我们便得到满足（１）的递推数列的通项公　式：ａ　一ｃ　入ｎ＿】＋ｃ：　。十…＋ｃｋ入２。　其中入　，入：，…　是其特征方程的ｋ个互不相同　的根，Ｃ　，Ｃ　・・Ｃ　由上面方程组唯一确定。　２．适合（１）的数列其特征方程有重根，这时方程　（２）即是　（Ｘ一入１）　１（ｘ一入２）　：…（ｘ一入　）　ｍ＝＝：Ｏ　（ｋ　＋ｋ　＋…＋ｋ　一ｋ）　线性递归数列　（仿照前面构造以下ｋ个数列　１，入ｌ，　入　，　入　…，入　０，入１，２Ｘ　，　３Ｘ　…（ｎ一１）　－●●　●●●　●●●　●●●　●●●　●●●　０，入ｌ。２ｋｌ　入　。　３　ｌ。入　，　…（ｎ一１）　ｌ　入　。　１．入２，　入；．　入　…，入　。　０，入　，２Ｘｉ，　３Ｘ；　…（ｎ一１）　０，入２，２ｋ２一　入；，　３ｋ！　入　，　…（ｎ一１）　！。。入：　１，入　，Ｘ　＊－，　入ｉ　，　…入　。　０，入　，２入：　．　３入ｉ　．　…（ｎ一１）入　Ｏ，入　，２　ｍ一　入ｉ　，３ｋ，，，－Ｉ入　…（ｎ一１）　ｎ　入：：　首先，以上每一组ｋ　（ｉ一１，２…ｎ　）个数列分别适　合特征方程（ｘ一入．）　一　事实上，对任意的入　一入，ｋｉ—ｋ上式即足　Ｘｋｃｉ入ｘ　＋…（一１）　ｃ｝入　一０　得相应的（１）为　ａ　＋ｋ—ｃｉ入ａ　＋ｋ—ｌ＋…＋（一１）　ｃ　入　ａ　一０　（６）　设｛ｂ　｝是ｋ一１阶等差数列，那么｛ｂ　｝是ｋ阶线　性递归数列Ｌ】　，且　ｂｌ１＋ｋ—ｃ　＋ｋ＿ｌ＋…＋（一１）　ｃ　一０　（７）　（７）两边同乘以　入　一　ｂ　＋ｋ—ｃ｛入（Ｘ，，＋ｋ￣－Ｚｂ　＋ｋ—１）＋…　＋（一１）　（　—ｂ　）一Ｏ　（８）　于是ａ　一入一　ｂ　适合（６），反之，若ａ　一　ｂ　适　合（６），那么　ｂ　｝是ｋ一１阶等差数列，并且是ｎ的　ｋ一１次多项式，所以　ａ　一（Ｃ１＋Ｃ？”＋…＋Ｃｋｎ　）　其中Ｃ　，Ｃ　，…Ｃ　由初始条件唯一确定。　其次，由性质１知（＊）中Ｉｌｌ组数列的线性组合　适合递推公式（１）。最后，得这种情形下通项为　ａ　一　（ｃ　＋ｃ　！ｎ＋…÷Ｃｉｋ　ｎｋ，－Ｉ）　其中Ｃ　Ｃ　…Ｃｉｋ　由初始条件ｋ个，通过解方　程确定。　参考资料：　［１］余元希．田万海．毛宏德．初等代数研究［Ｍ］．北京：高教　出版社出版．２００２．２．４６６．　１３。＿——