I read quite a while ago this proof of Binet's formula. ( I am not 100% sure this is the way it was presented, but it gives an idea. I'm not approving of this method or saying it is correct.)
Let $\hat{S}$ be an operator such that
$$\hat{S}a_n =a_{n+1}$$
Then, we can define Fibonacci's numbers this way
$$\hat{S}^2a_n =\hat{S}a_n+a_n$$
Solving for $\hat{S}$ gives
$$\left(\hat{S}^2-\hat{S}-1\right)a_n=0$$
Since $a_n\neq 0$ for all Fibonacci numbers, we necesarrily need:
$$\hat{S}^2-\hat{S}-1=0$$
This gives
$$\hat{S} = \frac{1\pm\sqrt{5}}{2}$$
But $$\hat{S}^n a_1 = a_n$$ and $a_1 = 1$.
Then they explain that since $\hat{S} = \dfrac{1\pm\sqrt{5}}{2}$ "it is natural to expect $a_n$ to be a linear combination of the $n$-th powers of $\phi$ and $1-\phi$", i.e.
$$a_n = A\phi^n+B(1-\phi)^n$$
Now we simply find $A$ and $B$ by equating to some know values, and get
$$a_n = \frac{\phi^n-(1-\phi)^n}{\sqrt{5}}$$ which is Binet's formula.
Could you explain what are the formal basis for this type of proofs/solutions to this problems and what is the motivation for the last supposition?