Why polynomial combinations of exponentials are the solution for homogenous linear recursion equations?

Question

The solution of Fibonacci recursion

$$ f_n = f_{n-2} + f_{n-1} $$

is sequence

$$ f_n = C_1 x_1^n + C_2 x_2^n $$

where we get $x_{12}$ from the characteristic equation of the recursion

$$ x^2 = x + 1 $$

and then get $C_1$ and $C_2$ from $f_0 = 0$ and $f_1 = 1$ base cases.

This is indeed a solution but what is the proof that $f_n$ is only of the form $ f_n = C_1 x_1^n + C_2 x_2^n $ ?

Referring to differential equation theory, I ask for a uniqueness proof of this solution.

Answer 1

Are you familiar with generating functions? You can prove this quity easily using generating functions (if you're familiar with integral transforms: gf are basically discrete integral transforms). It goes something like this:

Assume that the recurrence has some solution $(f_n)_{n \in \mathbb{N}_0}$. Define the formal power-series $F(x) = \sum_{n=0}^\infty f_n x^n$. You can derive a functional equation for $F$ from the recurrence which you can the solve for $F$. Develop the resulting expression into a power series of the form we originally used to define $F$, and you'll get precisely the solution you stated. So thus we've shown any solution has this form.

I've written up a full version of this here https://stefanvolz.online/math/generating-functions/generating-functions-integral-transforms/ (although it's in German). Information on generating functions can be found in most combinatorics texts or for example in generatingfunctionology by Wilf.

EDIT: Thinking about it: both existence as well as uniqueness are trivial. Clearly a solutions exists since we can just compute it from the start values and the recursion. This also directly gives you the uniqueness, since the start values of any solution have to coincide such that the solution is actually a solution and via the recursion this fixes all other terms in the sequence.

Answer 2

Uniqueness proof.

First, if $a_0 = a_1 = 0$ and $$ a_n = a_{n-2} + a_{n-1}, \tag1$$ then $a_n = 0$ for all $n$.

Second, if you can find $x_1$ so that $x_1^2 = x_1 + 1$, then $x_1^n$ satisfies $(1)$. Then if you can find $x_1, x_2$, with $x_1 \ne x_2$ so that $x_1^n$ and $x_2^n$ both satisfy $(1)$, then $C_1 x_1^n+C_2 x_2^n$ satisfies $(1)$ for any constants $C_1, C_2$.

Lastly, if you can find $C_1, C_2$ so that $C_1+C_2 = f_0$ and $C_1x_1+C_2x_2=f_1$, then $a_n = f_n - (C_1x_1^n-C_2x_2^n)$ satisfies $(1)$ with $a_0=a_1=0$. Done.

Answer 3

The space of the sequences $(f_n)_n$ with $f_{n+2}=f_{n+1}+f_n$ for $n\geq 0$ is two-dimensional.

Let $(x_n)_n$ the sequence with $x_{n+2}=x_{n+1}+x_n$ for $n\geq 0$ and $x_0=1$ and $x_1=0$. Further let $(y_n)_n$ the sequence with $y_{n+2}=y_{n+1}+y_n$ for $n\geq 0$ and $y_0=0$ and $y_1=1$. We show, that every sequence $(f_n)_n$ with $f_{n+2}=f_{n+1}+f_n$ for $n\geq 0$ has the form $f_n=a\cdot x_n+b\cdot y_n$ for all $n\geq 0$ with some constants $a,b$. So take an arbitrary sequence $(f_n)_n$ with $f_{n+2}=f_{n+1}+f_n$ for $n\geq 0$ and define $a:=f_0$ and $b:=f_1$, you can easily prove inductively that $f_n=a\cdot x_n+b\cdot y_n$ for all $n\geq 0$.

Answer 4

Suppose you have a polynomial $p(x)$ - say a cubic in $x$ with roots $\alpha, \beta, \gamma$.

Let $q_n(x)=x^np(x)$ so that $q_n$ has roots $\alpha, \beta, \gamma$

Then $0=Aq_n(\alpha)+Bq_n(\beta)+Cq_n(\gamma)$ and alternatively, gathering the terms by powers gives a linear recurrence in the sums of powers of the roots.

It is worth writing it out to see what happens, as it seems like magic the first time.