Closed form for recurrence relations- A long battle

I am almost morally obligated to write this post. While preparing for Math Olympiads, I came across the closed form formula for linear recurrence relations pretty often. However, I never quite came across *any* source that explained *why* this worked. And in the 6 years since, I’ve looked far and wide. However today, in my first College Combinatorics class, I think I finally understood why this works.

Let $a_n=c_{n-1}a_{n-1}+c_{n-2}a_{n-2}+\dots+c_{n-k}a_{n-k}$ . Along with this, we also have the initial conditions $a_0=d_0, a_1=d_1,\dots,a_{k-1}=d_{k-1}$ .

Let us assume that there exists a geometric sequence which satisfies the same relation! We have no information about initial conditions. Just a geometric sequence. To make things more explicit, I’d like to point out that the initial conditions are probably completely different from those mentioned before. Let this geometric sequence be of the form $f_n=r^n$ . Plugging these powers of $r$ in the recurrence relation above, we solve for the roots of the $(n-k)$ degree polynomial. We get $n-k$ complex roots, possibly repeated.

Say the distinct roots that we get are $p_1,p_2,\dots,p_j$ , where $j\leq n-k$ . Each root satisfies the recurrence relation. Hence, so does $q_1p_1^i+q_2p_2^i+\dots+q_jp_j^i$ , where $q_1,q_2,\dots,q_j\in\Bbb{C}$ . This can be checked directly by plugging his linear combination in the recurrence relation above.

Now we determine the values of the $q_i$ ‘s by assuming that $q_1p_1^i+q_2p_2^i+\dots+q_jp_j^i$ satisfies the initial conditions given above. Remember that these initial conditions give rise to a *unique* sequence that satisfies the recurrence relation. Hence, if we can get values of $q_i$ ‘s that make $q_1p_1^i+q_2p_2^i+\dots+q_jp_j^i$ satisfy each initial condition, then we’re done. Does this always work out? Do we always get unique values for the $q_i$ ‘s? Only when the system of equations we generate is consistent. As soon as we get values for $q_i$ ‘s that satisfy this system of equations, it is easy to see that we’ve gotten the closed form function we wanted.

This method is analogous to a gamble. We assume that the desired closed form function is a linear combination of geometric sequences. If it indeed is, we’ll get values for the $q_i$ ‘s. If it is not, we shall not get consistent values for the $q_i$ ‘s. What is important to note that if we do get consistent values for the $q_i$ ‘s, then this is our desired closed form. We don’t need to check for any more conditions. Because a recurrence relation with $k$ dependant terms (in that $a_n=c_{n-1}a_{n-1}+\dots+c_{n-k}a_{n-k}$ ) and $k$ initial conditions is unique.