Editing Cyclotomic polynomial (section)

=== Periodic recursive sequences ===

The constant-coefficient [[Linear recurrence with constant coefficients|linear recurrences]] which are periodic are precisely the power series coefficients of rational functions whose denominators are products of cyclotomic polynomials. 

In the theory of combinatorial [[Generating function|generating functions]], the denominator of a rational function determines a linear recurrence for its power series coefficients. For example, the [[Fibonacci sequence]] has generating function <blockquote><math>F(x) = F_1x + F_2x^2 + F_3x^3 + \cdots = \frac{x}{1-x-x^2} ,</math></blockquote>and equating coefficients on both sides of <math>F(x)(1-x-x^2) = x</math> gives <math>F_n - F_{n-1} - F_{n-2} = 0</math> for <math>n\geq 2</math>.  
<p>
Any rational function whose denominator is a divisor of <math>x^n - 1</math> has a recursive sequence of coefficients which is periodic with period at most ''n''. For example,</p> <blockquote><math>P(x) = -\frac{1+2x}{\Phi_6(x)} = \frac{1+2x}{1-x+x^2}
= \sum_{n\geq 0} P_n x^n 
= 1 + 3 x + 2 x^2 - x^3 - 3 x^4 - 2 x^5 + x^6 + 3 x^7 + 2 x^8 + \cdots</math> </blockquote>has coefficients defined by the recurrence <math>P_n - P_{n-1} + P_{n-2} = 0</math> for <math>n\geq 2</math>, starting from <math>P_0=1, P_1=3</math>. But <math>1-x^6 = \Phi_6(x)\Phi_3(x)\Phi_2(x)\Phi_1(x)</math>, so we may write <blockquote><math>P(x) = \frac{(1+2x)\Phi_3(x)\Phi_2(x)\Phi_1(x)}{1 - x^6}
 = \frac{1 + 3 x + 2 x^2 - x^3 - 3 x^4-2 x^5}{1 - x^6}, </math></blockquote>which means <math>P_n - P_{n-6} = 0 </math> for <math>n\geq 6</math>, and the sequence has period 6 with initial values given by the coefficients of the numerator.