Say we have Fibonacci recurrence:
$ F_{n+2}=F_{n+1}+F_n$, with $F_0=1,F_1=1$
We can write $F_n = a \alpha^n + b \beta ^n$, so how do we use Newton's polynomials to determine the value of $\alpha^r + \beta ^r$ without calculating the value of $\alpha$ and $\beta$?
The sequences $(α^n)_{n\in\Bbb N}$ and $(β^n)_{n\in\Bbb N}$ are solutions of the recurrence equation, and so is their sum $(G_n=α^n+β^n)_{n\in\Bbb N}$. The canonical basis of the solution space is composed of the sequences $(F_{n-2})_{n\in\Bbb N}$ and $(F_{n-1})_{n\in\Bbb N}$, so that $$ G_n=G_0\cdot F_{n-2}+G_1\cdot F_{n-1}=2⋅F_{n−2}+1⋅F_{n−1}=F_{n-2}+F_n. $$