Proving that $5^n+6^n$ and $5^{n+1}+6^{n+1}$ are coprime for all $n \in \mathbb{N}^*$ I need to prove, using Bézout's identity, that $5^n+6^n$ and $5^{n+1}+6^{n+1}$ are coprime for all $n \in \mathbb{N}^*$. I know that if they are coprime there exist $u,v \in \mathbb{Z}$ such that:
$u(5^n+6^n)+v(5^{n+1}+6^{n+1})=1$,
but I am unsure on how to proceed from here. Any help would be much appreciated.

Let $$a_n=5^n+6^n$$
Since $5,6$ are the roots of $$0=(x-5)(x-6)=x^2-11x+30$$  we deduce that the $a_n$ satisfy the recursion $$a_n=11a_{n-1}-30a_{n-2}\quad a_0=2\quad a_1=11$$
From this it is clear that if any $a_n,a_{n-1}$ have a common factor for any $n$, that factor also divides $a_{n-2}$. (Note:  we have $\gcd(a_n,30)=1$ for all $n$ so we can disregard the coefficient of the $a_{n-2}$ term). Since $a_0,a_1$ have no common factors, we are done.
