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$.