记$A(n)=\sum_{i=1}^{k}x_i^n$，若 $A(i)=a_i,i\in\{1,2,\cdots,k\}$，则$A(n)$是否存在递推公式？
猜测源自以下问题的推广：
已知$x+y=1$，$x^2+y^2=2$。求$x^3+y^3$与$x^4+y^4$的值(一般地，求$x^n+y^n$)?
【解】
由$x+y=1,x^2+y^2=2$得$x+y=1,xy=-\frac{1}{2}$，由韦达定理知$x,y$是方程$t^2-t-\frac{1}{2}=0$的两根。
利用$t^2=t+\frac{1}{2}$代入$x^3+y^3$与$x^4+y^4$可降幂至二次及以下，易得两式的值。
然而若要一般地求$x^n+y^n$，固然亦可不断迭代降幂，但显失优雅，能否求得通项公式？或退而求其次求得递推公式？
$$
(x^2-x- \frac{1}{2})+(y^2-y-\frac{1}{2})=0 \
$$
$$
\Rightarrow x^n(x^2-x-\frac{1}{2})+y^n(y^2-y-\frac{1}{2})=0 \
$$
$$
\Rightarrow (x^{n+2}-x^{n+1}-\frac{1}{2}x^n)+(y^{n+2}-y^{n+1}- \frac{1}{2}y^n)=0 \
$$
$$
\Rightarrow (x^{n+2}+y^{n+2})-(x^{n+1}+y^{n+1})-\frac{1}{2}(x^n+y^n)=0 \
$$
$$
\Rightarrow (x^{n+2}+y^{n+2})=(x^{n+1}+y^{n+1})+\frac{1}{2}(x^n+y^n) \
$$
得$A(n+2)=A(n+1)+\frac{1}{2}A(n)$。
