Another way to go about proving Binet's Formula As I showed in another question of mine, it is easy to prove that
$$\tag{1}\phi^{n+1} =F_{n+1} \phi+F_{n }$$
given $F_1=1$ , $F_2=1$ , $F_{n+1}=F_n+F_{n-1}\text{ ; }n\geq2$.
Now, extending $(1)$  to negative and zero indices naturally yields:
$$\eqalign{
  & {F_{ 0}} = 0  \cr 
  & {F_{ - 1}} = 1  \cr 
  & {F_{ - 2}} =  - 1  \cr 
  & {F_{ - 3}} = 2  \cr 
  & {F_{ - 4}} =  - 3  \cr 
  & {F_{ - n}} = {\left( { - 1} \right)^{n+1}}{F_{n}} \cr} $$
From this one has
$${\phi ^{  - n}} = {\left( { - 1} \right)^{n + 1}}\left( {{F_{n }}\phi  - {F_{n + 1}}} \right)$$
A few examples:
$$\eqalign{
  & {\phi ^{ - 1}} = \phi  - 1  \cr 
  & {\phi ^{ - 2}} = 2 - \phi   \cr 
  & {\phi ^{ - 3}} = 2\phi  - 3 \cr} $$
Then one has that
$$\eqalign{
  & {\left( { - \frac{1}{\phi }} \right)^n} = {F_{n + 1}} - {F_n}\phi   \cr 
  & {\phi ^n} = {F_n}\phi  + {F_{n - 1}} \cr} $$
and consequently
$$\eqalign{
  & {\phi ^n} + {\left( { - \frac{1}{\phi }} \right)^n} = {F_n}\phi  + {F_{n - 1}} + {F_{n + 1}} - {F_n}\phi   \cr 
  & {\phi ^n} + {\left( { - \frac{1}{\phi }} \right)^n} = {F_{n + 1}} + {F_{n - 1}}  \cr 
  & {\phi ^n} + {\left( { - \frac{1}{\phi }} \right)^n} = {L_n} \cr} $$
How can this be put into an acceptable proof? (Note that given the relation between Lucas and Fibonacci numers, this straightforwardly gives Binet's Formula:
$${F_n} = \frac{1}{{\sqrt 5 }}\left[ {{\phi ^n} - {{\left( { - \frac{1}{\phi }} \right)}^n}} \right]$$
 A: Below is a proof of the uniqueness theorem for second order recurrences, which is employed in Will's answer. The proof generalizes to higher-order recurrences. It is a discrete analog of the better-known result for differential equations, using variation of parameters (see this answer, and see my my 2004/4/27 sci.math post for references).
Theorem $\ $  If  $\rm\:f,g,h\: $ are solutions of the recurrence 
$$\rm \qquad\quad\ \     y''\: =\ p\ y' + q\ y,\ \ \ where\ \ \ y'(n)\, :=\, y(n\!+\!1) $$
with $ $ Wronskian (Casoratian) $\rm\ \  W = g\:h'-g'h \ne 0\:$    
then $\rm\,\exists\,\ \color{#c00}{ constants}\ \ c,d\,$ such that    $\rm\: f  = c\: g  + d\: h,\ \ \rm\color{#c00}{i.e.\ \ c'=c,\ d' = d}$ 
Proof $\ $ The equations $[0],[1]$ below have unique solution $\rm\:(c,d)\:$ via det $\rm = W \ne 0.$ 
$\rm[0]\qquad           f\  =\ c\: g \: + d\: h $ 
$\rm[1]\qquad           f' =\ c\: g' + d\: h'$
Now  $\rm\:q\:[0] + p\:[1]\:$  yields: 
$\rm[2]\qquad  q\:f+p\:f'\: =\ f''\: =\ c\: g'' + d\: h''\ $  via  $\rm\ \ q\:g+p\:g'\: =\ g'',\ \ q\:h+p\:h'\: =\ h''$ 
$\rm[3]\qquad           0\  =\ (c'-c)\:g' \:+ (d'-d)\:h'\:\ \ $  via  $\ \ [0]'-[1]$ 
$\rm[4]\qquad           0\  =\ (c'-c)\:g'' + (d'-d)\:h''\ \ $  via  $\ \ [1]'-[2]$ 
$[3],[4]$ have solution $\rm\:(c'\!-c,d'\!-d) = (0,0),\:$ 
unique by  $\rm\:det = W' = g'\:h''-g''\:h' \ne 0.\:$ Therefore $\rm\:c,d\:$ are constants, 
since  $\rm\:c' = c\:$  means  $\rm\:c(n+1) = c(n).\quad $ QED
Remark $\ $ Note  $\rm\, W = g\:h'-g'h = 0 \iff g/h =g'/h' = (g/h)'\iff g/h = c\,$ constant.
A: The set of sequences $x_n$ that have the property that $x_{n+2} = x_{n+1} + x_n,$ with, say, real number values, makes a vector space over the reals of dimension 2. Taking the two roots of $\lambda^2 = \lambda + 1,$ the larger being
$$ \phi = \frac{1 + \sqrt 5}{2}  $$ and the smaller being $-1 / \phi,$ any such sequence, including index shifts, whatever you like, is a linear combination of two basis sequences,
$$ \ldots, 1/\phi, 1, \phi,  \phi^2, \ldots    $$  and
$$ \ldots, - \phi, 1, -1 / \phi, 1/ \phi^2, \ldots    $$
where I am demanding that the element with value 1 have index 0 in both sequences. If I have any favorite sequence with $x_0, x_1$ specified, the equation to be solved for coefficients $A,B$ are
$$ A + B = x_0, \; \; \; A \phi - B / \phi = x_1.   $$
So
$$   
 \left(  \begin{array}{cc}
  1 & 1  \\
   \phi  & -1/\phi  
\end{array} 
  \right)  
 \left(  \begin{array}{c}
  A   \\
   B  
\end{array} 
  \right) \; \; = \; \;
  \left(  \begin{array}{c}
  x_0   \\
   x_1  
\end{array} 
  \right).
  $$
still composing...
$$   
 \left(  \begin{array}{c}
  A   \\
   B  
\end{array} 
  \right) \; \; = \; \; \frac{-1}{\sqrt 5}
 \left(  \begin{array}{cc}
  -1/\phi & -1  \\
   -\phi  & 1  
\end{array} 
  \right)  
  \left(  \begin{array}{c}
  x_0   \\
   x_1  
\end{array} 
  \right).
  $$
getting there...
Evidently you are taking  $x_0 = 0, x_1 = 1,$ so we get
$$   
 \left(  \begin{array}{c}
  A   \\
   B  
\end{array} 
  \right) \; \; = \; \; \frac{-1}{\sqrt 5}
 \left(  \begin{array}{cc}
  -1/\phi & -1  \\
   -\phi  & 1  
\end{array} 
  \right)  
  \left(  \begin{array}{c}
  0   \\
   1  
\end{array} 
  \right)  \; \; = \; \; 
  \left(  \begin{array}{c}
  1 / \sqrt 5   \\
   -1/ \sqrt 5  
\end{array} 
  \right)
.
  $$
My first basis sequence has elements labelled $y_n = \phi^n,$ and the second has $z_n = (-1/\phi)^n,$ so the Fibonacci sequence obeys  $$  x_n = \frac{1}{\sqrt 5} \; \; \phi^n \; \; \;  - \; \; \;  \frac{1}{\sqrt 5} \; \; \left( \frac{-1}{\phi} \right)^n. $$
A: I might as well point out how to use your way. We have the following two equations:
$$\varphi^{n+1}=F_{n+1}\varphi+F_{n} \tag{1}$$
$$(-1/\varphi)^n=F_{n+1}-F_n\varphi \tag{2}$$
For $(1)$, decrease $n$ by $1$, and for $(2)$ do the same but then divide both sides by $\varphi$. We obtain
$$\varphi^n=F_n\varphi+F_{n-1} \tag{a}$$
$$-(-1/\varphi)^n=F_n/\varphi-F_{n-1} \tag{b}$$
Now add $\rm(a)$ and $\rm(b)$ together and divide by $\varphi+1/\varphi=\sqrt{5}$ to obtain Binet's. This is analogous to what you did for Lucas numbers.
