VietaTheorem LinearRecursion Intermediate

Problem - 3321
If $m^2 = m+1, n^2-n=1$ and $m\ne n$, compute $m^7 +n^7$.

Because $m\ne n$, we find $m$ and $n$ are two roots of equation $$x^2-x-1=0$$ Let $y_k=m^k + n^k$. Then it must hold $y_{k+2}-y_{k+1}-y_k=0$ (see the book  Competition Algebra ), or $$y_{k+2}=y_{k+1}+y_k$$ It follows that: \begin{align} y_0 &=& m^0 + n^0 &=& 2\\ y_1 &=& m^1 + n^1 &=& 1\\ y_2 &=& y_1 + y_0 &=& 3\\ y_3 &=& y_2 + y_1 &=& 4\\ y_4 &=& y_3 + y_2 &=& 7\\ y_5 &=& y_4 + y_3 &=& 11\\ y_6 &=& y_5 + y_4 &=& 18\\ y_7 &=& y_6 + y_5 &=& 29 \end{align} Therefore the answer is $m^7 + n^7=y_7=\boxed{29}$.

report an error