Let $a^n = a^{n - 1} + a^{n -2}$. Show that for any $A, B$, $F(n) = Aa^n + Bb^n$ satisfies Fibonacci recurrence relation. $$\begin{align*}
F(n) &= Aa^n + Bb^n\\
&= A(a^{n-1}+a^{n-2}) + B(b^{n-1}+b^{n-2}) \\
&= Aa^{n -1} + Aa^{n-2} + Bb^{n -1} + Bb^{n-2}\\
&= a^{n -1} (A + A^{a-1}) + b^{n - 2} (B + bB)
\end{align*}$$
Use $$ \color{red}{ a > 1; \; \; b = \frac{-1}{a}.}   $$
Would that work?
edit: Suppose recurrence relation given by $F(n) = F(n - 1) + F(n - 2)$ grows at the same rate as some function $a^n$. Then, $a^n = a^{n -1} + a^{n -2}$ by substitution. $a^n \to a^2 = a + 1$. One of its roots is negative and we call it $b$. Since $a^n, b^n$ satisfy Fibonacci recurrence relation, $F(n) = Aa^n + Bb^n$ also does. That's what I want to prove.

Let me try rewriting the question and giving an answer:
Restated question
Suppose that $a$ and $b$ are the two solutions to $x^2 - x - 1 = 0$, so that we have $a^2 = a + 1$ (and similarly for $b$) and hence also 
\begin{align}
a^n &= a^{n-1} + a^{n-2}& \text{ (**) }
\end{align}
for $n \ge 2$, and similarly for $b$. 
Show that for any $A, B$, the function 
$$
F(n) = A a^n + B b^n
$$
has the Fibonacci property, i.e., that
$$
F(n) = F(n-1) + F(n-2)
$$
for all integers $n \ge 2$. 
Solution to this rephrased problem
Suppose $n$ is any integer greater than 2. Then 
\begin{align}
F(n) 
&= Aa^n + B b^n & \text{ by definition of $F$}\\
&= A(a^{n-1} + a^{n-2}) + B (b^{n-1} + b^{n-2}) & \text{ by equation (**) }\\
&= A a^{n-1} + A a^{n-2} + Bb^{n-1} + B b^{n-2} & \text{ by distributive law, twice }\\
&= A a^{n-1} + B b^{n-1} + A a^{n-2} + B b^{n-2} & \text{ by commutative lawfor addition }\\
&= \left( A a^{n-1} + B b^{n-1} \right) + \left( A a^{n-2} + B b^{n-2} \right )& \text{parens added for clarity }\\
&= F(n-1)+ F(n-2) & \text{definition of $F$, twice }.
\end{align}
The second and last steps are justified because we have $n \ge 2$, in case you were wondering about that bit. So we've shown that $F$ satisfies the Fibonacci recurrence for all $n \ge 2$, as required.  
