问题

已知 $x_1+x_2=1$ ， $x_1x_2=-1$ ，求 $x_1^7+x_2^7=?$

这是小朋友问我的一个题目，第一感觉就是用求根公式解方程组，分别求出 $x_1$ 和 $x_2$ 的解，然后代入 $x_1^7+x_2^7$ ，然后解决完毕，呵呵！

解法一：粗暴解法

先给出一个定理: 设一元二次方程 $ax^2+bx+c=0(a,b,c\in R, a \ne 0)$ 的两个根 $x_1$ 和 $x_2$ ，
由求根公式可以得到
$x_{1,2}=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$

根据条件可以得到 $x_1$ 和 $x_2$ 是一元二次方程 $x^2-x-1=0$ 的两个根。由一元二次方程的求根公式可知 $x_{1,2}=\frac{1 \pm \sqrt5}{2}$
然后
$x_1^7+x_2^7=(\frac{1+\sqrt5}{2})^7+(\frac{1-\sqrt5}{2})^7 = 29$

问题如果用计算器计算无理数，可能会丢失精度，更何况没有计算器，对于这种无理数的高次幂运算需要用到二项式定理，太费CPU了，这不是正解。

解法二：迭代法

先求解根的低次幂和
$s_1=x_1+x_2=1$
$s_2=x_1^2+x_2^2=(x_1+x_2)^2-2x_1x_2=3$
$s_3=x_1^3+x_2^3=(x_1+x_2)^3-3x_1x_2(x_1+x_2)=4$
$s_4=x_1^4+x_2^4=(x_1^2+x_2^2)^2-2(x_1^2x_2^2)^2=7$
然后惊奇地发现 $s_2=s_1+0,s3=s1+s2,s4=s3+s2$ ,这不是斐波那契额数列Fibonacci sequence的特性吗？

于是就直接得出
$s_5=s_4+s_3=11$
$s_6=s_5+s_4=18$
$s_7=s_6+s_5=29$

所以 $x_1^7+x_2^7=29$ ，解决完毕，但是这毕竟是猜想，结果虽然是正确的，但是不严谨！而且如果题目的条件变化了，是不是都满足Fibonacci sequence的特性呢？由此引出了这样的问题：如果我们知道了两个未知数的和以及乘积，是否可以知道所有根的任意次幂的和呢？是不是可以更加泛化一下呢？

泛化问题

已知 $x_1+x_2=a$ ， $x_1x_2=b$ ，
求 $x_1^n+x_2^n=? 其中a,b都是常数，n \in N$

解：

令 $s_n=x_1^n+x_2^n$ ，则

$s_n=x_1^{n-1}x_1+x_2^{n-1}x_2$
$s_n=x_1^{n-1}(a-x_2)+x_2^{n-1}(a-x_1)$
$s_n=ax_1^{n-1}-x_1^{n-1}x_2+ax_2^{n-1}-x_1x_2^{n-1}$
$s_n=a(x_1^{n-1}+x_2^{n-1})-x_1x_2(x_1^{n-2}+x_2^{n-2})$
$s_n=a(x_1^{n-1}+x_2^{n-1})-b(x_1^{n-2}+x_2^{n-2})$
于是得到了以下的递推公式:
$s_n=as_{n-1}-bs_{n-2}$

那么对于原始问题已知 $a=1,b=-1$
可以得到 $s_n=s_{n-1}+s_{n-2}$
由此验证了解法二的严谨性。

延拓新的问题

如果 $x_1,x_2$ 没有实数解，以上方法是否适用?

看一个例子,对于泛化的公式,如果 $a=b=2$ ，
即 $s_1=x_1+x_2=2, x_1x_2=2$
显然 $x_{1,2}=1 \pm i$
那么 $s_2=x_1^2+x_2^2=(1+i)^2+(1-i)^2=0$
按照递推公式
$s_3=2s_2-2s_1=-4$
$s_4=2s_3-2s_2=-8$
$s_5=2s_4-2s_3=-8$
$s_6=2s_5-2s_4=0$
$s_7=2s_6-2s_5=16$
$s_8=2s_7-2s_6=32$
$s_9=2s_8-2s_7=32$
$s_{10}=2s_9-2s_8=0$
$s_{11}=2s_{10}-2s_9=-64$
貌似也ok，待证明

总结一下泛化问题

对于已知 $x_1+x_2=a$ ， $x_1x_2=b$ ，
求 $s_n =x_1^n+x_2^n=? 其中a,b都是常数，n \in N$

就会有 $s_n=as_{n-1}-bs_{n-2}, 其中s_0=2,s_1=a$

最后用python代码实现一下

# a是和, b是积, n是幂
def solution(a,b,n):
    if(n == 0):
        return 2
    if(n == 1):
        return a
    return a*solution(a,b,n-1)- b*solution(a,b,n-2)

运行结果

>>> print(solution(1,-1,0))
2
>>> print(solution(1,-1,1))
1
>>> print(solution(1,-1,2))
3
>>> print(solution(1,-1,3))
4
>>> print(solution(1,-1,4))
7
>>> print(solution(1,-1,5))
11
>>> print(solution(1,-1,6))
18
>>> print(solution(1,-1,7))
29

然后

>>> print(solution(1,-1,100))
# 等了好久都没算出来
# 容易理解的算法性能差，性能好的算法不容易理解，这就是生活！！！！

经典优化方案，空间换时间:

def solution(a,b,n):
    sn,s0,s1 = 0, 2, a
    for i in range(1, n):
        sn = a*s1 - b*s0
        s0 = s1
        s1 = sn
    return sn

测试100

>>> print(solution(1,-1,100))
792070839848372253127
# 计算结果秒出了

某初中数学题的解法