Complex Roots and Oscillatory Linear Recurrences

From Complex Roots to Real Oscillations

A real recurrence can have complex characteristic roots even though every term of the sequence is real. When the roots are a conjugate pair, their contributions combine into a real expression involving sine and cosine. The resulting sequence may alternate in sign or oscillate in a more gradual pattern, while a factor raised to the index controls its scale.

Consider a real sequence \((x_n)_{n\geq 0}\) satisfying a second-order homogeneous recurrence \(x_{n+2}+a x_{n+1}+b x_n=0\) for every integer \(n\geq 0\), where \(a,b\in\mathbb R\). Two initial values, \(x_0\) and \(x_1\), determine the later terms. The characteristic polynomial of this recurrence is \(p(\lambda)=\lambda^2+a\lambda+b\); its roots are called the characteristic roots. To see why they are relevant, substituting a trial sequence \(x_n=\lambda^n\) gives \(\lambda^{n+2}+a\lambda^{n+1}+b\lambda^n=\lambda^n p(\lambda)\). Thus a root produces a sequence that satisfies the recurrence.

Writing the roots this way separates their shared size \(r\) from their opposite angles. Their sum is \(2r\cos\theta\), and their product is \(r^2\). Consequently, the recurrence with these roots can be written \(x_{n+2}-2r\cos\theta\,x_{n+1}+r^2x_n=0\). This form makes the sine and cosine structure visible.

Proof. The recurrence has the form \(x_{n+2}-2r\cos\theta\,x_{n+1}+r^2x_n=0\), since the sum and product of its characteristic roots are \(2r\cos\theta\) and \(r^2\). The angle-addition identities give \(\cos((n+2)\theta)-2\cos\theta\cos((n+1)\theta)+\cos(n\theta)=0\), and the same identity holds with sine in place of cosine. Multiplying these identities by \(r^{n+2}\) shows that both \(r^n\cos(n\theta)\) and \(r^n\sin(n\theta)\) satisfy the recurrence. Their linear combination with real coefficients \(C,D\) therefore satisfies it as well.

At \(n=0\), that combination equals \(C\), so matching \(x_0\) requires \(C=x_0\). At \(n=1\), it equals \(r(C\cos\theta+D\sin\theta)\). Since \(0<\theta<\pi\) implies \(\sin\theta\ne0\), matching \(x_1\) gives \(D=(x_1/r-C\cos\theta)/\sin\theta\). Thus the displayed formula has the prescribed initial values. Finally, the recurrence determines each next term from the two preceding terms: \(x_{n+2}=2r\cos\theta\,x_{n+1}-r^2x_n\). Any two solutions with the same \(x_0,x_1\) must therefore agree at \(x_2\), then at \(x_3\), and successively at every later index. The formula is the unique solution. \(\square\)

Testing for a Nonreal Root Pair

Proof. The quadratic formula gives the roots \(\lambda=(-a\pm\sqrt{a^2-4b})/2\). If \(a^2-4b<0\), the square root is purely imaginary and the roots are nonreal conjugates. The inequality also gives \(b>a^2/4\geq0\), so \(r=\sqrt b\) is positive. The proposed cosine and sine satisfy \(\cos^2\theta+\sin^2\theta=\dfrac{a^2+4b-a^2}{4b}=1\), and the sine is positive. Hence they specify an angle in \((0,\pi)\), and the two roots are \(r(\cos\theta\pm i\sin\theta)\). Conversely, if the roots are \(\alpha+i\beta\) and \(\alpha-i\beta\) with \(\beta\ne0\), then their sum and product give \(a=-2\alpha\) and \(b=\alpha^2+\beta^2\). It follows that \(a^2-4b=4\alpha^2-4(\alpha^2+\beta^2)=-4\beta^2<0\). This proves both directions. \(\square\)

Two Further Forms of the Oscillation

The sine-and-cosine expression records the initial conditions directly, but it can also be written as a single shifted cosine. If \(C,D\) are not both zero, set \(R=\sqrt{C^2+D^2}\) and choose an angle \(\phi\) such that \(\cos\phi=C/R\) and \(\sin\phi=D/R\). Then the angle-addition identity gives \(C\cos(n\theta)+D\sin(n\theta)=R\cos(n\theta-\phi)\). Thus the solution is \(x_n=Rr^n\cos(n\theta-\phi)\). If \(C=D=0\), every term is zero, and no phase angle is needed. This form describes an oscillation whose angle advances by \(\theta\) at each step, scaled by \(Rr^n\).

For real coefficients, the discriminant test can often be used before calculating any roots. A negative discriminant means the recurrence has the oscillatory form above; a zero or positive discriminant does not give a nonreal conjugate pair. In particular, a repeated real root is not covered by this formula. The condition \(\sin\theta\ne0\) is essential when solving for \(D\), and is guaranteed here by the roots being nonreal.

Common Pitfall: Losing the Factor \(r\)

The initial value \(x_1\) is not \(C\cos\theta+D\sin\theta\); the formula has an additional factor \(r\) at index \(1\). For the first worked example, the incorrect calculation \(D=(x_1-C\cos\theta)/\sin\theta\) gives \(D=(2-\tfrac12)/(\sqrt3/2)=\sqrt3\). Substituting this value into the claimed solution gives \(x_1=2(\tfrac12+\sqrt3\cdot\tfrac{\sqrt3}{2})=4\), contradicting the required initial value \(x_1=2\). The correct calculation divides \(x_1\) by \(r\) first: \(D=(x_1/r-C\cos\theta)/\sin\theta=(1-\tfrac12)/(\sqrt3/2)=1/\sqrt3\). Always substitute the proposed constants back into both initial values before using the resulting sequence.

The formula also provides a simple scale bound. Since \(|\cos(n\theta)|\leq1\) and \(|\sin(n\theta)|\leq1\), it follows that \(|x_n|\leq r^n(|C|+|D|)\). This bound does not remove the oscillation; it separates a bound on the size from the changing sine-and-cosine factor. The central procedure is therefore: identify the conjugate roots, write their modulus and angle, use \(x_0,x_1\) to find \(C,D\), and verify the initial terms against the recurrence.