Closed form for recurrence relations- A long battle

by ayushkhaitan3437

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.