一个自然数幂和公式的推导

一个自然数幂和公式的推导陆多俊中国科学院沈阳计算技术研究所，辽宁沈阳（110004）E-mail：[e-mail]摘要：本文从对递推关系求解的角度，推导出自然数幂和的组合数表达形式。为计算机求解幂和问题提供了方法和依据。关键词：幂和，形式幂级数，生成函数中图分类号：O122.71.引言自然数的幂和指的是对于α，n∈N，形如1()niSniαα==∑的求和式。这是一个古典的数学问题，从古希腊阿基米德开始研究，一直是经典数学问题研究热点之一。本文通过对递推关系的求解，推导出自然数幂和的一种表示。对α∈N，()Snα可以递归地表示为00,()-11.aanSnS(n)+nnα=⎧=⎨≥⎩下面来求解这个递推关系。做形式幂级数：0()()nnAxSnxα∞==∑（1）将递推关系代入（1）得11()(0)(1)nnnnAxSSnxnxααα∞∞==−=−+∑∑1()nnxAxnxα∞==+∑所以，11()1nnAxnxxα∞==−∑。令0()nnTxnxαα∞==∑，于是，1()()1AxTxxα=−（2）其中，()Txα是数列{}kα的生成函数，记为{}Gkα。求出形式幂级数A（x）的nx项对应的系数即是()Snα。{}Gkα的推导以已经知道的生成函数作为基础，归纳推导出{}Gkα系数满足的递推关系。为了便于推导先介绍生成函数的一个性质：设数列{}ka的生成函数0{}()nkknGaAxax∞===∑,kkbka=⋅,那么'{}()kGbxAx=⋅。其中，'()Ax是()Ax的一阶导数。由2{}(1)xGkx=−，得22'3{}{}(1)xxGkxGkx+=⋅=−。设11(1)iiaiaxG{k}xαα=+=−∑，其中iaN∈，记1()iiifxaxαα==∑为{}Gkα的分子，那么1'{}{}GkxGkαα+='112(1)()(1)(1)(1)iiiiiixaxaxxxαααα==+−−−+=−∑∑11112[(1)(1)](1)iiiiaiaiaxaxxxααααα−+=+++−+++=−∑（3）12()(1)fxxαα++=−可以看出，当把生成函数1{}Gkα+的分子多项式1()fxα+写为升幂或降幂的形式时，它的系数可以由{}Gkα的分子多项式系数递推地得出。即1()fxα+的系数是()fxα系数的线性和。由1()fxx=和22()fxxx=+的系数，根据（3）可以写出()fxα系数的递推三角阵：…图1()fxα系数的递推关系1()fxα+的系数对应于第1α+行。这就是我国古代数学家李善兰所发现的乘方垛求和公式中的“李氏数”[1]。在图1中，根据（3）第i行第j列的“李氏数”满足下面递推关系：111(1)iiijjjLijLjL−−−=+−+11i,ji（4）其中，每一行的首项和末项为1。由（4）容易得出()fxα的系数是对称的。例如，2344()1111fxxxxx=+++，进而有，234451111{}(1)xxxxGkx+++=−。3.()Snα的求解由（2）1()()1AxTxxα=−，而()Txα的分子系数满足（3）所表示的递推关系。设1()jjjfxLxααα==∑，那么1()1()1(1)fxAxxxαα+=⋅−−2()(1)fxxαα+=−。又，11{()}(1)mkkmGx+−=−[2]。令2mα=+。于是，1()(){()}mkkAxfxGα+−=⋅1(){()}kkfxGαα++=⋅可以求得nx的系数：11()()njjnjjSnLαααα+−+−==⋅∑()njjjLαααα+−++==∑。（5）其中，jLα（1≤j≤α）为多项式()fxα的jx项的系数，即“李氏数”。例如，432145555()()11()11()()nnnnSn++++=+++。根据图1和（5）式，很容易写出()Snα一般组合形式的表达式。4.结论()Snα的计算方法有很多种，大多数都是通过递推的形式。本文给出了自然数幂和以简单递推关系为基础的组合数表示及推导过程。从组合表示形式很容易计算出自然数幂和的多项式形式。从而简化幂和的计算过程。参考文献[1]吴文俊．《世界著名数家传记》[M]，北京：科学出版社，1995[2]孙淑玲，许胤龙．《组合数学引论》[M]，合肥：中国科学技术大学出版社，2002.4ADeductionoftheformularyforsummingpowerednaturalnumbersLuDuojunTheShenyanginstituteofcomputingtechnology.ChineseAcademyofSciences,Shenyang(110004)AbstractThispaperdeducestheformularyofthesummationofpowerednaturalnumbers,bysolvingtherecursion.Itoffersmethodsandaccordsforcomputingthesummationofpowerednaturalnumbersusingcomputers.Keywords:summationofpowerednaturalnumbers,formedpowerseries,generatedfunction