算法分析中递推式的一般代数解法

算法分析中经常遇到需要求解递推式的情况，即将递推式改写为等价的封闭形式。例如汉诺塔问题的时间复杂度递推形式为

，可以解出封闭形式为

（设初始状态

）。

因为递推式求解的重要性，许多算法书籍对其有专门介绍。Donald Knuth在Concrete Mathematics一书中多个章节都涉及递推式求解方法。算法导论也在第四章中专门论述的这个主题。

在这些相关论述中，主要介绍了一些启发式方法，这些方法往往需要一些特殊的技巧和灵感才能完成。

而本文将论述一种纯代数式的方法，这种方法将求解递推式转化为求解一个多项式的根和求解一组线性方程组，这样就使得整个求解过程不依赖于太多技巧，因此具有更好的易用性。

本文首先会给出两个例子：如何使用纯代数方法求解斐波那契数列和汉诺塔递推式；然后会借助线性代数论述这种方法背后的数学意义，说明线性递推式与线性方程的内在联系以及这种解法的数学原理；最后将例子中的方法推广到一般情况。

示例

例1：斐波那契数列

斐波那契数列大家应该很熟悉了，这里不再赘述，直接进入问题。

问题

设斐波那契数列为由如下递推式定义的数列：

求解

的封闭形式（也就是斐波那契数列的通项公式）。

求解

首先忽略初始条件，考虑递推式

。可以对解的形式进行一个猜测

（这个不是瞎猜的，实际上可以证明线性递推式都遵循这种形式）。那么，递推式可以重写为：

这样问题被转化为一个一元二次方程的求根问题。利用求根公式可得：

因此得到递推式的一个通解：

即其中

和

为任意实数。下一步要代入初始条件解出

和

。根据n为0和1时的初始条件，可得：

解得

，

。因此最终解为：

例2：汉诺塔

汉诺塔的时间复杂度通常使用递归式定义，在这个例子中将使用代数方法求解其封闭形式。

问题

汉诺塔的时间复杂度为

，求解其封闭形式。

求解

这里并不能直接使用例1中的方法，因为右边除了递推项外，还有一个非递推项1，用线性代数的语言说，这个线性递推式是非齐次的。

可以回想一下线性代数中求解非齐次方程组通解的方法：1）求解其齐次部分的通解。2）求其一个特解，将特解加到通解上即得非齐次方程组通解。

我们用类似的方法求解汉诺塔时间复杂度递推式。首先，忽略后面的1，则得到一个齐次线性递推式：

转化为多项式方程：

因为方程是一次多项式，我们直接得到了其解为2。因此齐次递推式的通解为

，其中c为任意常数。

然后我们需要求得

的一个特解，解是一个以n为变量的函数。我们可以先从常数试起，设特解为

，带入得

，解得

。因此，原递推式的通解为：

最后我们求解常数c。

将初始条件

带入，得

，因此

。代入原通解，得汉诺塔时间复杂度递推式的封闭形式为：

数学原理

上面两个例子可能有些同学看的不是很明白，其中提到了一些线性代数术语。在这一章节中，我们分析上述解法的数学原理，看看递推式是如何与线性代数关联起来的。

线性递推式的一般化

斐波那契数列和汉诺塔递推式可以看成线性递推式的特例，下面给出线性递推式的一般定义：

我们将满足如下递推关系的递推式称为线性递推式：

其中

是只与n有关系的一个函数。如果

，则称递推式为齐次此，否则称为非齐次的。齐次递推式一定有平凡解

。

注意仅有递推式是不能求得

的唯一解，因此递推关系式只能给出一个通解。只有当下列初始条件确定后，才有可能给出

的唯一特解。

齐次递推式求解定理

下面先考虑齐次线性递推式的求解。定理如下：

设有线性齐次递推式

360docimg_501_360docimg_502_360docimg_503_360docimg_504_360docimg_505_360docimg_506_360docimg_507_360docimg_508_360docimg_509_360docimg_510_360docimg_511_360docimg_512_360docimg_513_360docimg_514_360docimg_515_360docimg_516_360docimg_517_360docimg_518_360docimg_519_360docimg_520_

另设多项式方程360docimg_521_360docimg_522_360docimg_523_360docimg_524_360docimg_525_360docimg_526_360docimg_527_360docimg_528_360docimg_529_360docimg_530_360docimg_531_360docimg_532_360docimg_533_360docimg_534_360docimg_535_360docimg_536_360docimg_537_360docimg_538_360docimg_539_360docimg_540_360docimg_541_360docimg_542_360docimg_543_360docimg_544_360docimg_545_360docimg_546_360docimg_547_360docimg_548_360docimg_549_360docimg_550_360docimg_551_360docimg_552_的根是360docimg_553_360docimg_554_360docimg_555_360docimg_556_360docimg_557_360docimg_558_360docimg_559_360docimg_560_360docimg_561_360docimg_562_，我们先讨论不存在重根的情况，也就是说k个根互不相等。

则360docimg_563_360docimg_564_360docimg_565_360docimg_566_的通解为：

360docimg_567_360docimg_568_360docimg_569_360docimg_570_360docimg_571_360docimg_572_360docimg_573_360docimg_574_360docimg_575_360docimg_576_360docimg_577_360docimg_578_360docimg_579_360docimg_580_360docimg_581_360docimg_582_360docimg_583_360docimg_584_360docimg_585_360docimg_586_360docimg_587_360docimg_588_360docimg_589_360docimg_590_

并且对于任意的初始情况

360docimg_591_360docimg_592_360docimg_593_360docimg_594_360docimg_595_360docimg_596_360docimg_597_360docimg_598_360docimg_599_360docimg_600_360docimg_601_360docimg_602_360docimg_603_360docimg_604_360docimg_605_360docimg_606_360docimg_607_360docimg_608_360docimg_609_360docimg_610_360docimg_611_360docimg_612_360docimg_613_360docimg_614_360docimg_615_360docimg_616_

都存在一组解360docimg_617_360docimg_618_360docimg_619_360docimg_620_360docimg_621_360docimg_622_360docimg_623_使得递推式成立

定理的证明

要证明以上定理，主要需要证明两部分。一是证明多项式根的线性组合可以满足递推式，二是证明任意初始条件下总有解。

可满足性证明

首先来证明360docimg_624_360docimg_625_360docimg_626_360docimg_627_360docimg_628_360docimg_629_360docimg_630_360docimg_631_360docimg_632_360docimg_633_360docimg_634_360docimg_635_360docimg_636_360docimg_637_360docimg_638_360docimg_639_360docimg_640_360docimg_641_360docimg_642_360docimg_643_360docimg_644_360docimg_645_360docimg_646_360docimg_647_可以满足递推式。

360docimg_648_360docimg_649_360docimg_650_360docimg_651_360docimg_652_360docimg_653_360docimg_654_360docimg_655_360docimg_656_360docimg_657_360docimg_658_360docimg_659_360docimg_660_360docimg_661_360docimg_662_360docimg_663_360docimg_664_360docimg_665_360docimg_666_360docimg_667_360docimg_668_360docimg_669_360docimg_670_360docimg_671_360docimg_672_360docimg_673_360docimg_674_360docimg_675_360docimg_676_360docimg_677_360docimg_678_360docimg_679_360docimg_680_360docimg_681_360docimg_682_360docimg_683_360docimg_684_360docimg_685_360docimg_686_360docimg_687_360docimg_688_360docimg_689_360docimg_690_360docimg_691_360docimg_692_360docimg_693_经过变换可以改写为360docimg_694_360docimg_695_360docimg_696_360docimg_697_360docimg_698_360docimg_699_360docimg_700_360docimg_701_360docimg_702_360docimg_703_360docimg_704_360docimg_705_360docimg_706_360docimg_707_360docimg_708_360docimg_709_360docimg_710_360docimg_711_360docimg_712_360docimg_713_360docimg_714_360docimg_715_360docimg_716_360docimg_717_360docimg_718_360docimg_719_360docimg_720_360docimg_721_360docimg_722_360docimg_723_360docimg_724_360docimg_725_360docimg_726_360docimg_727_360docimg_728_360docimg_729_360docimg_730_360docimg_731_360docimg_732_360docimg_733_360docimg_734_360docimg_735_360docimg_736_360docimg_737_360docimg_738_360docimg_739_360docimg_740_360docimg_741_

假设360docimg_742_360docimg_743_360docimg_744_360docimg_745_360docimg_746_360docimg_747_360docimg_748_，因为360docimg_749_360docimg_750_360docimg_751_，所以两边除以360docimg_752_360docimg_753_360docimg_754_360docimg_755_，得到360docimg_756_360docimg_757_360docimg_758_360docimg_759_360docimg_760_360docimg_761_360docimg_762_360docimg_763_360docimg_764_360docimg_765_360docimg_766_360docimg_767_360docimg_768_360docimg_769_360docimg_770_360docimg_771_360docimg_772_360docimg_773_360docimg_774_360docimg_775_360docimg_776_360docimg_777_

因此这个多项式和原递推式同解，因此多项式的每个根q的几何级数360docimg_778_360docimg_779_都是原递推式的一个解。同时，根的线性组合360docimg_780_360docimg_781_360docimg_782_360docimg_783_360docimg_784_360docimg_785_360docimg_786_360docimg_787_360docimg_788_360docimg_789_360docimg_790_360docimg_791_360docimg_792_360docimg_793_360docimg_794_360docimg_795_360docimg_796_360docimg_797_360docimg_798_均满足原递推式（可以带入验证）。

任意初始值有解证明

下面要证明对于任意初始条件，均存在适当的常数360docimg_799_360docimg_800_360docimg_801_360docimg_802_360docimg_803_360docimg_804_360docimg_805_。

将

360docimg_806_360docimg_807_360docimg_808_360docimg_809_360docimg_810_360docimg_811_360docimg_812_360docimg_813_360docimg_814_360docimg_815_360docimg_816_360docimg_817_360docimg_818_360docimg_819_360docimg_820_360docimg_821_360docimg_822_360docimg_823_360docimg_824_360docimg_825_360docimg_826_360docimg_827_360docimg_828_360docimg_829_360docimg_830_360docimg_831_

带入通解公式，得到一个线性方程组

360docimg_832_360docimg_833_360docimg_834_360docimg_835_360docimg_836_360docimg_837_360docimg_838_360docimg_839_360docimg_840_360docimg_841_360docimg_842_360docimg_843_360docimg_844_360docimg_845_360docimg_846_360docimg_847_360docimg_848_360docimg_849_360docimg_850_360docimg_851_360docimg_852_360docimg_853_360docimg_854_360docimg_855_360docimg_856_360docimg_857_360docimg_858_360docimg_859_360docimg_860_360docimg_861_360docimg_862_360docimg_863_360docimg_864_360docimg_865_360docimg_866_360docimg_867_360docimg_868_360docimg_869_360docimg_870_360docimg_871_360docimg_872_360docimg_873_360docimg_874_360docimg_875_360docimg_876_360docimg_877_360docimg_878_360docimg_879_360docimg_880_360docimg_881_360docimg_882_360docimg_883_360docimg_884_360docimg_885_360docimg_886_360docimg_887_360docimg_888_360docimg_889_360docimg_890_360docimg_891_360docimg_892_360docimg_893_360docimg_894_360docimg_895_360docimg_896_360docimg_897_360docimg_898_360docimg_899_360docimg_900_360docimg_901_360docimg_902_360docimg_903_360docimg_904_360docimg_905_360docimg_906_360docimg_907_360docimg_908_360docimg_909_360docimg_910_360docimg_911_360docimg_912_360docimg_913_360docimg_914_360docimg_915_360docimg_916_

此时问题转化为证明此方程组对于必然有解，下面就要用到线性代数的知识了。这个方程组的系数行列式为：

360docimg_917_360docimg_918_360docimg_919_360docimg_920_360docimg_921_360docimg_922_360docimg_923_360docimg_924_360docimg_925_360docimg_926_360docimg_927_360docimg_928_360docimg_929_360docimg_930_360docimg_931_360docimg_932_360docimg_933_360docimg_934_360docimg_935_360docimg_936_360docimg_937_360docimg_938_360docimg_939_360docimg_940_360docimg_941_360docimg_942_360docimg_943_360docimg_944_360docimg_945_360docimg_946_360docimg_947_360docimg_948_360docimg_949_360docimg_950_360docimg_951_360docimg_952_360docimg_953_360docimg_954_360docimg_955_360docimg_956_360docimg_957_360docimg_958_360docimg_959_360docimg_960_360docimg_961_360docimg_962_360docimg_963_360docimg_964_360docimg_965_360docimg_966_360docimg_967_360docimg_968_360docimg_969_360docimg_970_360docimg_971_360docimg_972_360docimg_973_360docimg_974_360docimg_975_360docimg_976_360docimg_977_360docimg_978_360docimg_979_360docimg_980_

这个行列式就是非常著名Vandermonde行列式，所以

360docimg_981_360docimg_982_360docimg_983_360docimg_984_360docimg_985_360docimg_986_360docimg_987_360docimg_988_360docimg_989_360docimg_990_360docimg_991_360docimg_992_360docimg_993_360docimg_994_360docimg_995_360docimg_996_360docimg_997_360docimg_998_360docimg_999_360docimg_1000_360docimg_1001_360docimg_1002_

上面我们假设了多项式各个根均互异，因此行列式的值不等于0，这意味着系数矩阵的秩为k。有线性代数知识可知，这表明对于任意初始值360docimg_1003_360docimg_1004_360docimg_1005_360docimg_1006_360docimg_1007_360docimg_1008_360docimg_1009_360docimg_1010_360docimg_1011_，方程组均有唯一解。

证毕。

顺便说一下，上面的多项式叫特征多项式。其根叫特征根。

通用解法

通过上面的数学分析，我们得到了一个解线性递推式的通用方法。

齐次递推式

设有齐次递推式

360docimg_1012_360docimg_1013_360docimg_1014_360docimg_1015_360docimg_1016_360docimg_1017_360docimg_1018_360docimg_1019_360docimg_1020_360docimg_1021_360docimg_1022_360docimg_1023_360docimg_1024_360docimg_1025_360docimg_1026_360docimg_1027_360docimg_1028_360docimg_1029_360docimg_1030_360docimg_1031_360docimg_1032_360docimg_1033_360docimg_1034_360docimg_1035_360docimg_1036_360docimg_1037_360docimg_1038_360docimg_1039_360docimg_1040_360docimg_1041_360docimg_1042_360docimg_1043_360docimg_1044_360docimg_1045_360docimg_1046_360docimg_1047_360docimg_1048_360docimg_1049_360docimg_1050_360docimg_1051_360docimg_1052_360docimg_1053_360docimg_1054_360docimg_1055_360docimg_1056_360docimg_1057_

我们可以写出其特征多项式方程

360docimg_1058_360docimg_1059_360docimg_1060_360docimg_1061_360docimg_1062_360docimg_1063_360docimg_1064_360docimg_1065_360docimg_1066_360docimg_1067_360docimg_1068_360docimg_1069_360docimg_1070_360docimg_1071_360docimg_1072_360docimg_1073_360docimg_1074_360docimg_1075_360docimg_1076_360docimg_1077_360docimg_1078_360docimg_1079_360docimg_1080_360docimg_1081_360docimg_1082_360docimg_1083_360docimg_1084_360docimg_1085_360docimg_1086_360docimg_1087_360docimg_1088_360docimg_1089_

解出其k个根360docimg_1090_360docimg_1091_360docimg_1092_360docimg_1093_360docimg_1094_360docimg_1095_360docimg_1096_。如果k个根互异（但可以有复根），则原递推式的通解为

360docimg_1097_360docimg_1098_360docimg_1099_360docimg_1100_360docimg_1101_360docimg_1102_360docimg_1103_360docimg_1104_360docimg_1105_360docimg_1106_360docimg_1107_360docimg_1108_360docimg_1109_360docimg_1110_360docimg_1111_360docimg_1112_360docimg_1113_360docimg_1114_360docimg_1115_360docimg_1116_360docimg_1117_360docimg_1118_360docimg_1119_360docimg_1120_

然后将初始条件360docimg_1121_360docimg_1122_360docimg_1123_360docimg_1124_360docimg_1125_360docimg_1126_360docimg_1127_360docimg_1128_360docimg_1129_带入组成线性方程组

360docimg_1130_360docimg_1131_360docimg_1132_360docimg_1133_360docimg_1134_360docimg_1135_360docimg_1136_360docimg_1137_360docimg_1138_360docimg_1139_360docimg_1140_360docimg_1141_360docimg_1142_360docimg_1143_360docimg_1144_360docimg_1145_360docimg_1146_360docimg_1147_360docimg_1148_360docimg_1149_360docimg_1150_360docimg_1151_360docimg_1152_360docimg_1153_360docimg_1154_360docimg_1155_360docimg_1156_360docimg_1157_360docimg_1158_360docimg_1159_360docimg_1160_360docimg_1161_360docimg_1162_360docimg_1163_360docimg_1164_360docimg_1165_360docimg_1166_360docimg_1167_360docimg_1168_360docimg_1169_360docimg_1170_360docimg_1171_360docimg_1172_360docimg_1173_360docimg_1174_360docimg_1175_360docimg_1176_360docimg_1177_360docimg_1178_360docimg_1179_360docimg_1180_360docimg_1181_360docimg_1182_360docimg_1183_360docimg_1184_360docimg_1185_360docimg_1186_360docimg_1187_360docimg_1188_360docimg_1189_360docimg_1190_360docimg_1191_360docimg_1192_360docimg_1193_360docimg_1194_360docimg_1195_360docimg_1196_360docimg_1197_360docimg_1198_360docimg_1199_360docimg_1200_360docimg_1201_360docimg_1202_360docimg_1203_360docimg_1204_360docimg_1205_360docimg_1206_360docimg_1207_360docimg_1208_360docimg_1209_360docimg_1210_360docimg_1211_360docimg_1212_360docimg_1213_360docimg_1214_

解线性方程组得唯一解360docimg_1215_360docimg_1216_360docimg_1217_360docimg_1218_360docimg_1219_360docimg_1220_360docimg_1221_360docimg_1222_360docimg_1223_。带回通解公式则得到递推式的最终解

360docimg_1224_360docimg_1225_360docimg_1226_360docimg_1227_360docimg_1228_360docimg_1229_360docimg_1230_360docimg_1231_360docimg_1232_360docimg_1233_360docimg_1234_360docimg_1235_360docimg_1236_360docimg_1237_360docimg_1238_360docimg_1239_360docimg_1240_360docimg_1241_360docimg_1242_360docimg_1243_360docimg_1244_360docimg_1245_360docimg_1246_360docimg_1247_360docimg_1248_360docimg_1249_360docimg_1250_

非齐次递推式

对于非齐次递推式

360docimg_1251_360docimg_1252_360docimg_1253_360docimg_1254_360docimg_1255_360docimg_1256_360docimg_1257_360docimg_1258_360docimg_1259_360docimg_1260_360docimg_1261_360docimg_1262_360docimg_1263_360docimg_1264_360docimg_1265_360docimg_1266_360docimg_1267_360docimg_1268_360docimg_1269_360docimg_1270_360docimg_1271_360docimg_1272_360docimg_1273_360docimg_1274_360docimg_1275_360docimg_1276_360docimg_1277_360docimg_1278_360docimg_1279_360docimg_1280_360docimg_1281_360docimg_1282_360docimg_1283_360docimg_1284_360docimg_1285_360docimg_1286_360docimg_1287_360docimg_1288_360docimg_1289_360docimg_1290_360docimg_1291_360docimg_1292_360docimg_1293_360docimg_1294_360docimg_1295_360docimg_1296_360docimg_1297_360docimg_1298_360docimg_1299_360docimg_1300_360docimg_1301_360docimg_1302_360docimg_1303_360docimg_1304_360docimg_1305_360docimg_1306_360docimg_1307_360docimg_1308_360docimg_1309_

可以首先按上面的方法求解其齐次部分的通解360docimg_1310_360docimg_1311_。然后求得其一个特解360docimg_1312_360docimg_1313_，则非齐次递推式的通解为

360docimg_1314_360docimg_1315_360docimg_1316_360docimg_1317_360docimg_1318_

然后用同样的方法带入初始值，通过线性方程组求出个常量参数带回即可（具体可参见例2）。

有重根的情况

上面的解法只针对特征根互异，如果有重根的话，则上述方法会无效。不过只要经过一定处理也可以有通用方法求解，因有点复杂，本文不在针对重根情况进行叙述。关于重根情况下的求解，有感兴趣的同学可以参考线性代数或微分方程相关文献。