寻求两变量n次幂和的非递归表达式（基于和s与积p）

嘿，你提到的这个非递归公式其实是对称多项式领域里的经典结论，完全不用一步步递推，特别适合计算高次幂和。

先直接给你通用的非递归通项公式，和你给出的n=11的例子完全匹配：

对于两个变量$a$和$b$，记$s = a+b$，$p=ab$，那么$n$次幂和的非递归表达式为：

$$a^n + b^n = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k \cdot \frac{n}{n-k} \cdot \binom{n-k}{k} \cdot s^{n-2k} p^k$$

为什么这个公式成立？ #

这个公式的来源可以从两个角度理解：

• 递推反向推导：我们知道幂和的递推式是$a^n + b^n = s(a^{n-1}+b{n-1}) - p(a^{n-2}+b{n-2})$，把这个递推关系展开到最底层（直到$a^0+b0=2$或$a^1+b1=s$），整理后就能得到这个组合形式的非递归表达式。
• 生成函数法：构造幂和的生成函数$G(x) = \sum_{n=0}^\infty (a^n + b^n)xn$，化简后得到$G(x) = \frac{2 - sx}{1 - sx + px^{2}$，对这个分式做泰勒展开，提取$x}n$的系数就能得到上述通项。

对应你给出的n=11的例子验证 #

代入$n=11$，$k$从0到5（因为$\lfloor 11/2 \rfloor=5$）：

• $k=0$：$(-1)^0 \cdot \frac{11}{11} \cdot \binom{11}{0} s^{11}p0 = s^{11}$
• $k=1$：$(-1)^1 \cdot \frac{11}{10} \cdot \binom{10}{1} s^9p1 = -11s^9p$
• $k=2$：$(-1)^2 \cdot \frac{11}{9} \cdot \binom{9}{2} s^7p2 = 44s^7p2$
• $k=3$：$(-1)^3 \cdot \frac{11}{8} \cdot \binom{8}{3} s^5p3 = -77s^5p3$
• $k=4$：$(-1)^4 \cdot \frac{11}{7} \cdot \binom{7}{4} s^3p4 = 55s^3p4$
• $k=5$：$(-1)^5 \cdot \frac{11}{6} \cdot \binom{6}{5} s^1p5 = -11sp^5$

把这些项加起来，正好就是你给出的右边表达式，完全一致。

实际计算优势 #

对于高次幂（比如n=100），用这个公式直接求和到$k=50$即可，不需要像递推那样从低次一步步算到高次，效率提升非常明显。

备注：内容来源于stack exchange，提问作者Sam101110