Let $a= \frac{1+\sqrt{5}}{2}$ and $b= \frac{1-\sqrt{5}}{2}$. Prove that for all $c,d \in \mathbb{N}$ that $g_n = ca^n + db^n$ satisfies $g_{n+2} = g_{n+1} + g_{n}$ for all $n\in \mathbb{N}$.
I'm stuck on how to write a proof for this problem. I tried induction but wasn't able to get anywhere reasonable. I know I can solve $g_n$ for $n=0,1$ and obtain some $c,d$ but I am unable to do it for all cases.
How can I solve this problem?
It mostly amounts to using backwards the method that yields the formula of the Fibonacci sequence $$ca^{n+2}+db^{n+2}-ca^{n+1}-db^{n+1}-ca^n-db^n=\\ ca^n(a^2-a-1)+db^n(b^2-b-1)=\cdots\quad ?$$
Of course, there are two things in the above expression that you do not want to calculate, and fortunately you need not do it.