How do you prove uniqueness of solution of homogeneous linear recurrences?

Question

I was following the MIT 6.042 course on OCW (that don't cover generating function on the lectures, sorry if the answer is easier by doing that method).

Recall a linear homogeneous recurrences is of the form:

$$T(n) = \sum^{n}_{i=1} a_i T(n-i)$$

It is shown that the solution can be obtained from the roots of the characteristic equation:

$$x^n = \sum^{n}_{i=1}a_i x^{n-i}$$

and the combining them linearly to form the homogenous solutions.

It is clear to me that indeed, that the roots and their linear combinations are a valid solution. However, what is not clear to me is the uniqueness of the solution (its also not clear that it did not "miss" out any other potential function that solves the recurrence that should have been included linearly in the solution to the homogeneous recurrence).

How does one go about proving that we did not miss some function that could have been part of the solution?

Said differently, say that the homogeneous solution to the linear recurrence is:

$$f(n) = \sum^{n}_{i=1}r_i(x,n)$$

where $r_i(x,n)$ is one of the roots of the characteristic polynomial (or a function of it in the case where there are repeated roots). How do you prove that this are all of terms that solves the recurrence? How are you able to rule out "crazy" functions such as $f(n) = e^{e^{e^{n^3 + log{n}}}}$ or any other infinite set of creative functions I could think? How do you show they ALL could NEVER solve the recurrence?

I am well aware that there a extremely similar question to this one here. Here is the link to it:

Uniqueness of solutions to linear recurrence relations

However I am unable to fully understand its solution and how its able to rule out this infinite set of alternative potential functions that could solve the recurrence.

For easy of reference I will post the solution given to that question and address the parts that don't make sense to me (also, look at the end of my question to understand the notation used in the following answer):

Yes, you can see it by observing that the set of all solutions is a vector space of dimension d; this holds because if you choose q1,…qd, the rest is clearly determined. The solutions {rni} are linearly independent (which can be shown by Vandermond determinant, for example), so they generate the whole space.

The first thing is, how do you justify or prove that the solutions is a vector space of dimension d? How does that rule out the possibility of the function $\log{\log \log \log {n^{2.777}}}$ to be a solutions? I know I could just try to plug them into the recurrence, but there is an infinite set of these, isn't there an easier way to reason about them and really get that the roots are the only solutions?

---

Reference of the notation used on the other question:

Recurrence:

$$q_n = q_{n-1} + c_2 q_{n-2} + \cdots + c_d q_{n-d}$$

Its characteristic polynomial $$p(t) = t^d - c_1 t^{d-1} - \cdots - c_{d-1} t - c_d$$

and if the roots are $r_1, \ldots, r_d$ (say distinct, for simplicity) then the solution is: $$q_n = k_1 r_1^n + \cdots k_d r_d^n$$

for any choice of coefficients $k_i$.

Answer 1

You can write the recurrence system as $X_{n+1} = M X_n$ where $X_0 \in\mathbf{R}^n$ is given, and then you see that the set of solutions is given by all $X_0$ possible, which is a vector space of dimension $d$ over $\mathbf{R}$. If you need more details on $M$ or the $X_n$'s tell me.

EDIT More "elaborate answer" as the OP politely asked for it :

1) First of all, you made a big mistake in the very definition of a sequence defined by a linear homogeneous recurrence. Indeed, at each step $n$, the $n$-th term of your sequence will depend on all $n-1$ previous terms. This is not the definition of a sequence defined by a linear homogeneous recurrence. The real and only definition (justifying the use of a polynomial after, use that would be useless and inappropriate in the case of your definition) is the following : $u_n = a_1 u_{n-1} + \ldots + a_d u_{n-d}$ for all $n$, with $u_0,\ldots,u_{d-1}$ given for a start. You'll tell if this is what you mean, but I think it is.

2) Now with this correct definition, consider the polynomial $P = T^d - a_1 T^{d-1} - \ldots - a_d$. Assuming that the roots of $P$ are $\alpha_1,\ldots,\alpha_e$ with $\alpha_i$ being a root with multiplicity $m_i$. (We then have $\alpha_1 + \ldots + \alpha_e = d$.) Then, the following sequences (and all linear combination thereof) verify our linear homogenous recurrence (I note the sequences in a map fashion) : $n\mapsto \alpha_1^n, \ldots, n\mapsto n^{\alpha_1 - 1} \alpha_1^n, \ldots, n\mapsto \alpha_e^n, \ldots, n\mapsto n^{\alpha_e - 1} \alpha_e^n$. (Exercise : check it.)

3) If you count the number of elements of the previous list of sequences, you'll count $\alpha_1 + \ldots + \alpha_e = d$ sequences, all linearly independant. The dimension of the solution space is therefore at least $d$. Now the point is to show that it is exactly $d$. (This is what interests you.) Everything is based of the following observation : you can rewrite your linear homoegenous recurrence $u_n = a_1 u_{n-1} + \ldots + a_d u_{n-d}$ as :

$\underbrace{\begin{bmatrix}u_n\\u_{n-1}\\ u_{n-2} \\ \vdots \\ u_{n-d+1} \end{bmatrix}}_{:= X_n \in \mathbf{R}^{d}} = \underbrace{\begin{bmatrix}a_{1} & a_{2} & \cdots & a_{d-1} & a_{d} \\ 1 & 0 & \cdots &0 & 0\\ 0 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \cdots & 1 & 0\end{bmatrix}}_{:=M \in \mathbf{M}_d (\mathbf{R})} \underbrace{\begin{bmatrix}u_{n-1} \\u_{n-2} \\ u_{n-3} \\ \vdots \\ u_{n-d} \end{bmatrix}}_{= X_{n-1}}$ where the first line defines the linear homegenous recurrence relations, and all other $d-1$ lines are dummy equations $u_{n-1} = u_{n-1}, u_{n-2} = u_{n-2}, \ldots u_{n-d+1} = u_{n-d+1}$. This is the matrix recurrence I was writing about above : $X_n = M X_{n-1}$.

Solutions of our linear homogenous equation and solution of this matrix linear recurrence are isomorphic. Indeed, note $S_1$ the space of solutions of our initial linear homogeneous equation and $S_2$ the space of solutions of $X_n = M X_{n-1}$. All solution of this linear recurrence are $X_n = M^n X_0$ with $X_0 \in \mathbf{R}^d$. (Same as geometric sequences in $\mathbf{R}$...) Now define a linear map from $S_2$ to $S_1$ by associating to a sequence $(X_n)_n$ veryfing $X_n = M X_{n-1}$ the real sequence $(u_n)_n$ verifying $u_n = a_1 u_{n-1} + \ldots + a_d u_{n-d}$ with $u_0 = x_1, \ldots, u_{d-1} = x_d$ where $X_0 = \begin{bmatrix} x_1 \\ \vdots \\ x_d \end{bmatrix}$ is the initial vector giving rise to the sequence $(X_n)_n$. Define a linear map from $S_1$ to $S_2$ by associating to a sequence $(u_n)_n$ verifying $u_n = a_1 u_{n-1} + \ldots + a_d u_{n-d}$ the vector sequence $(X_n)_n$ verifying $X_n = M^n X_0$ where $X_0 = \begin{bmatrix} x_1 \\ \vdots \\ x_d \end{bmatrix}$ with $x_1 = u_1, \ldots, x_d = u_{d-1}$. It is clear that the maps are inverse one to the other, showing that $S_1$ and $S_2$ are isomorphic vector spaces. We saw that $S_2$ is of dimension $d$ (because $X_0$ determines all the sequence, and you can choose it in whole $\mathbf{R}^d$). Therefore $S_1$ is also of dimension $d$, which shows that in (2) we indeed found all solutions.

Now if you're happy, don't hesitate to upvote ! ;-)