Several sources propose finding a general formula for the $n^{\text{th}}$ term of a sequence defined by a recurrence relation by assuming the term is defined by a power function.
E.g. consider the Fibonacci numbers:
$$u_{n+2}=u_{n+1}+u_n$$
$$u_0=u_1=1$$
Let $u_n=kx^n$:
$$x^2=x+1$$
$$x=\frac{1\pm\sqrt{5}}{2}$$
At this point it is usually stated that the double root implies two forms for $u_n$, both of which satisfy the recurrence.
$$u_{n1}=k_1\left(\frac{1+\sqrt{5}}{2}\right)^n$$
$$u_{n2}=k_2\left(\frac{1-\sqrt{5}}{2}\right)^n$$
Therefore the most general solution is a combinaton of the above two:
$$u_n=k_1\left(\frac{1+\sqrt{5}}{2}\right)^n + k_2\left(\frac{1-\sqrt{5}}{2}\right)^n$$
My question is – how can this step be justified? If you check on $u_{n1}$ being a general formula, it does not check out as you get inconsistent values for $k_1$ if $u_0$ and $u_1$ are considered:
$$u_0=k_1=1$$
$$u_1=k_1\left(\frac{1+\sqrt{5}}{2}\right)=1 => k_1 = \frac{2}{1+\sqrt{5}}$$
So this must mean the original assumption of $u_n=kx^n$ is incorrect in the first place?
Best Answer
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$.