The Fibonacci numbers are defined by a second-order linear recurrence equation:
$$F_{n+2} = F_{n+1} + F_n$$
This means we can treat the solution of $F_n$ in terms of $n$ as a problem in linear algebra involving only $2$-dimensional vectors. In some sense, what we are doing is modelling this as a dynamical process on a $2$-dimensional state space.
Let $V = \mathbb{R}^2$. We define a linear operator $T : V \to V$ by
$$T(x, y) = (y, x + y)$$
Notice that $T(F_{n}, F_{n+1}) = (F_{n+1}, F_{n+2})$, so you can think of $V$ as being a sliding $2$-entry window on the Fibonacci sequence and $T$ as the operator which advances the window along the Fibonacci sequence. The initial conditions $F_0 = 0, F_1 = 1$ then imply that
$$T^n(0, 1) = (F_n, F_{n+1})$$
so all we need to do to find $F_n$ in terms of $n$ is to find an effective way to compute iterates of the operator $T$!
Now, we get our hands dirty and represent $T$ as a matrix:
$$T = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$$
Imagine if we could somehow find an invertible matrix $P$ and a diagonal matrix $D$ such that $T = P D P^{-1}$; then, by matrix algebra, we would have $T^n = P D^n P^{-1}$, and it is easy to compute powers of diagonal matrices. The theory of eigenvectors and eigenvalues gives us one way to find such a factorisation of $T$. Notice that
$$\det (T - x I) = \det (P(D - x I)P^{-1}) = (\det P)(\det (D - x I))(\det P^{-1}) = \det (D - x I)$$
but a simple calculation shows
$$\det (D - x I) = \det \begin{pmatrix} \lambda_1 - x & 0 \\ 0 & \lambda_2 - x \end{pmatrix} = (\lambda_1 - x)(\lambda_2 - x)$$
so whatever $\lambda_1$ and $\lambda_2$ are, they must be the zeros of the polynomial
$$\det (T - x I) = \det \begin{pmatrix} -x & 1 \\ 1 & 1 - x \end{pmatrix} = x^2 - x - 1$$
which, surprise surprise, is the minimal polynomial of the golden ratio. So let $\lambda_1 = \frac{1}{2} (1 + \sqrt{5})$ and $\lambda_2 = \frac{1}{2} (1 - \sqrt{5})$. These are the eigenvalues of $T$. By construction, $\det (T - \lambda_1 I) = \det (T - \lambda_2 I) = 0$, so there must be non-zero vectors $\begin{pmatrix} x_1 \\ y_1 \end{pmatrix}$ and $\begin{pmatrix} x_2 \\ y_2 \end{pmatrix}$ such that
$$
T
\begin{pmatrix} x_1 \\ y_1 \end{pmatrix} =
\lambda_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix}
$$
$$
T
\begin{pmatrix} x_2 \\ y_2 \end{pmatrix} =
\lambda_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix}
$$
These vectors are called the eigenvectors of $T$. I leave you to verify that $x_1 = \lambda_1 - 1$, $y_1 = 1$, $x_2 = \lambda_2 - 1$, $y_2 = 1$ works, but there are other solutions.
Define the matrix $P$ by
$$P = \begin{pmatrix} x_1 & x_2 \\ y_1 & y_2 \end{pmatrix}$$
Notice that
$$\begin{pmatrix} x \\ y \end{pmatrix} =
\alpha_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} +
\alpha_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} =
P \begin{pmatrix} \alpha_1 \\ \alpha_2 \end{pmatrix}$$
so by linearity we have
$$T \begin{pmatrix} x \\ y \end{pmatrix} =
\lambda_1 \alpha_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} +
\lambda_2 \alpha_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} =
P \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} \begin{pmatrix} \alpha_1 \\ \alpha_2 \end{pmatrix}$$
but we can invert $P$ to find $\alpha_1$ and $\alpha_2$ in terms of $x$ and $y$, so we have obtained the desired factorisation of $T$ as $P D P^{-1}$ with $D$ diagonal. Putting everything together, we get the formula
$$T^n = P \begin{pmatrix} {\lambda_1}^n & 0 \\ 0 & {\lambda_2}^n \end{pmatrix} P^{-1}$$
and applying this to the vector $\begin{pmatrix} 0 \\ 1 \end{pmatrix}$ gives Binet's formula.
You’ve misunderstood the purpose of $k_1$ and $k_2$: they serve to pick out one of the infinitely many sequences satisfying the recurrence
$$u_{n+2}=u_{n+1}+u_n\,.\tag{1}$$
Let $\Sigma$ be the vector space of all sequences of real numbers; vector addition is defined termwise, so that
$$\langle x_n:n\in\Bbb N\rangle+\langle y_n:n\in\Bbb N\rangle=\langle x_n+y_n:n\in\Bbb N\rangle\,.$$
The sequences satisfying $(1)$ turn out to be a $2$-dimensional subspace of $\Sigma$. Let $\varphi=\frac12\left(1+\sqrt5\right)$ and $\hat\varphi=\frac12\left(1-\sqrt5\right)$, the two zeroes of $x^2-x-1=0$. Then the sequence $\langle\varphi^n:n\in\Bbb N\rangle$ and $\langle\hat\varphi^n:n\in\Bbb N\rangle$ are linearly independent sequences satisfying $(1)$, so every sequence satisfying $(1)$ is a linear combination of these two sequences. Thus, if $v=\langle v_n:n\in\Bbb N\rangle$ is a particular sequence satisfying $(1)$, there are constants $k_1$ and $k_2$, depending on $v$ such that
$$v_n=k_1\varphi^n+k_2\hat\varphi^n\tag{2}$$
for each $n\in\Bbb N$. One uses the initial values $v_0$ and $v_1$ to find $k_1$ and $k_2$.
The point here is that these values of $k_1$ and $k_2$ apply only to the specific sequence determined by the initial values $v_0$ and $v_1$. If $v_0=1$ and $v_1=\varphi$, then $k_1=1$ and $k_2=0$, and we get the sequence of powers of $\varphi$. If $v_0=1$ and $v_1=1$, substituting $n=0$ and $n=1$ into $(2)$ shows that $k_1+k_2=1$ and $k_1\varphi+k_2\hat\varphi=1$, and we get a very different pair of values for $k_1$ and $k_2$.
Best Answer
HINT $\rm\quad\ u_n =\: x^n\ \iff\ 0\ =\ x^{n+2}\:-\:x^{n+1}\:-\:x^n\ =\ (x^2-x-1)\ x^n\ =:\ f(x)\ x^n\:.\:$
Therefore, we infer that $\rm\ \phi^{\ n}\:$ and $\rm\ \bar\phi^{\ n}\:$ are solutions, where $\rm\:\phi,\ \bar\phi\:$ are the roots of $\rm\:f(x)\:.$
Thus by linearity $\rm\ g_n =\: c\ \phi^{\:n} +d\ \bar\phi^{\:n}\ $ is also a solution, for any constants $\rm\: c,\:d\:.$
By induction, solutions are uniquely determined by their initial conditions $\rm\:u_0,\:u_1,\:$ hence
$\begin{array}{rl} \qquad\qquad\rm g_n =\: f_n\!\! &\iff\quad\begin{array}{}\rm 0\: =\: f_0 =\: g_0 =\: c+d \\ \rm 1\: =\: f_1 =\: g_1 =\: c\ \phi + d\ \bar\phi\end{array} \\ &\iff\quad\rm d = {-}c,\quad c\: =\: \dfrac{1}{\phi-\bar\phi} \\ &\iff\quad\rm g_n =\: \dfrac{\phi^{\:n}-\bar\phi^{\:n}}{\phi\ -\ \bar\phi\ \ \ } \end{array}$
This is a prototypical example of the power of uniqueness theorems for proving equalities. Here the uniqueness theorem is that for linear difference equations (i.e. recurrences). While here the uniqueness theorem has a trivial one-line proof by induction, in other contexts such uniqueness theorems may be far less less trivial (e.g. for differential equations). As such, they may provide great power for proving equalities. For example, some of my prior posts.