While solving problem 2020 on this year’s AMC 1212A, I, along with many others quickly derived the recurrence relation cn=2cn−1+n−2c_n = 2c_{n-1}+n-2⁠, c1=1c_1 = 1 where cnc_n represents the sum of the elements of the nnth row. However, the question did not just ask for a recursion; it requested the value of c2023(mod10).c_{2023} . While my friends guessed the solution, or engineers inducted, I proceeded with a standard method: Characteristic Polynomials.

To start off, we require some big words that can be skimmed in a first reading. The main idea of this approach is that recurrences of the form cn=A⋅cn−1+B⋅cn−2+C⋅cn−3⋯+f(n)c_n = A\cdot c_{n-1} + B \cdot c_{n-2} + C \cdot c_{n-3} \dots + f(n) for constants A⁠,B⁠,C⁠,…A, B, C, \dots are satisfied by exponential solutions when f(n)=0f(n) = 0. Also, all these recurrence relations obey the superposition principle. In other words, if linearly independent b1⁠,b2⁠,b3…bkb_1, b_2, b_3 \dots b_k are particular solutions to cnc_n⁠, then the general form of cnc_n is a linear combination of b1⁠,b2⁠,b3…bkb_1, b_2, b_3 \dots b_k.

With the complex jargon out of the way, let’s first handle the homogeneous case, where f(n)=0.f(n) = 0.

This is best explained through example. Let’s derive the closed form equation of the recurrence fn=8fn−1+9fn−2f_n = 8f_{n-1} + 9f_{n-2} where f1=4f_1 = 4 and f2=32f_2 = 32⁠, a key step in problem 44 from the 20182018 USAJMO. Knowing that the particular solutions are exponential, we guess the solution to be of the form fn=λnf_n = \lambda^n for constant λ.\lambda. Now, the recurrence becomes λn=8λn−1+9λn−2⟺λ2−8λ−9=0.\lambda^n = 8\lambda^{n-1} + 9\lambda^{n-2} \Longleftrightarrow \lambda^2 - 8 \lambda - 9 = 0. Accordingly, the recurrence is satisfied when λ=9⁠,−1\lambda = 9, -1 or equivalently when fn=9nf_n = 9^n and when fn=(−1)n.f_n = (-1)^n. By the superposition principle, the general solution is fn=A⋅9n+B⋅(−1)n.f_n = A \cdot 9^n + B \cdot (-1)^n. The values of AA and BB may be found from the initial conditions, and are left as an exercise to the reader.

Indeed, the general procedure for a homogeneous recurrence is to set the solution as fn=λnf_n = \lambda^n and apply the superposition principle with the initial cases.

Now, what happens if f(n)f(n) is not zero, but a polynomial? Certainly, it is sometimes possible to use algebraic tricks to create a homogeneous relation. However, a sneaky method is to identify a polynomial solution to the recurrence. This solution would be the only non-exponential solution to the recurrence. Hence, by the superposition principle, the general solution is a linear combination of the homogeneous solution (pretend f(n)=0f(n) = 0) and this polynomial solution.

As an example, let’s return to the initial recurrence cn=2cn−1+n−2.c_n = 2c_{n-1} + n-2. If we were to use algebraic manipulation, we must eliminate n−2n-2 from the recurrence. For instance, we may apply cn−1=2cn−2+n−3(1)cn=2cn−1+n−2(2)cn+1=2cn+n−1(3) c_{n-1} &= 2c_{n-2} + n-3 \quad(1) c_{n} &= 2c_{n-1} + n-2 \quad(2) c_{n+1} &= 2c_{n} + n-1 \quad(3) Now, (3)+(1)−2⋅(2)(3) + (1) - 2 \cdot (2) yields cn+1−4cn+5cn−1−2cn−2=0⁠, c_{n+1}-4c_{n}+5c_{n-1}-2c_{n-2} = 0, which is homogeneous. Setting cn=λnc_n = \lambda^n yields λ3−4λ2+5λ−2=0⟺(λ−2)(λ−1)2=0⁠,\lambda^3 - 4\lambda^2 + 5\lambda -2 = 0 \Longleftrightarrow (\lambda - 2)(\lambda-1)^2 = 0, so λ=1⁠,1⁠,2\lambda = 1,1,2. With the double root (triple, quadruple, etc. roots work similarly), we invoke the general theory of recurrence relations to say that the particular solutions are n(1)nn(1)^n and 1n1^n; the other particular solution is 2n.2^n. As such, cn=A2n+Bn(1)n+C1nc_n = A2^n + Bn(1)^n + C1^n. Solving for the specific constants is left to the reader.

Finally, we conclude by presenting an application of the sneakier method. We note that the degree of any polynomial solution must be less than or equal to 11; otherwise, the degree of the RHS exceeds that of the LHS. Therefore, if the polynomial solution is cn=Dn+Ec_n = Dn + E⁠, we may obtain D=−1⁠,E=0.D = -1, E = 0.

For the homogeneous version, we have cn=2cn−1c_n = 2c_{n-1} which solves to the particular case of cn=2nc_n = 2^n. The general solution is therefore cn=A⋅2n+B(−n).c_n = A\cdot 2^n + B(-n). Solving for the constants is left to the reader.

Curiously enough, the process to solve linear differential equations is almost identical to the methods presented in this article.