Something looks familiar about this recurrence...

Algebra Level 5

Define a sequence of polynomials P 0 P_0 , P 1 P_1 , \ldots by the recurrence P 0 ( x ) = 1 P_0(x) = 1 , P 1 ( x ) = x P_1(x) = x , P n + 1 ( x ) = 2 x P n ( x ) P n 1 ( x ) P_{n+1}(x) =2xP_n(x) - P_{n-1}(x) . Let S = P 2017 ( i 2 ) S = \left |P_{2017}' \left (\dfrac{i}{2} \right ) \right | and T = P 17 ( i 2 ) T = \left |P_{17}' \left (\dfrac{i}{2} \right )\right | , where i i is the imaginary unit. Then S T \dfrac{S}{T} is a rational number with fractional part m n \dfrac{m}{n} , where m m and n n are relatively prime positive integers. Compute m m .


The answer is 4142.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Mark Hennings
Nov 8, 2017

If we write P n ( i x ) = i n Q n ( x ) P_n(ix) = i^nQ_n(x) then we have Q 0 ( x ) = 1 Q_0(x) = 1 , Q 1 ( x ) = x Q_1(x) = x and Q n ( x ) = 2 x Q n 1 ( x ) + Q n 2 ( x ) Q_n(x) \; = \; 2xQ_{n-1}(x) + Q_{n-2}(x) Thus Q 0 ( 1 2 ) = 1 Q_0(\tfrac12) = 1 , Q 1 ( 1 2 ) = 1 2 Q_1(\tfrac12) = \tfrac12 and Q n ( 1 2 ) = Q n 1 ( 1 2 ) + Q n 2 ( 1 2 ) Q_n(\tfrac12) \; = \; Q_{n-1}(\tfrac12) + Q_{n-2}(\tfrac12) so that Q n ( 1 2 ) = 1 2 L n Q_n(\tfrac12) = \tfrac12L_n for all n 0 n \ge 0 . Moreover Q 0 ( x ) = 0 Q_0'(x) = 0 , Q 1 ( x ) = 1 Q_1'(x) = 1 and Q n ( x ) = 2 x Q n 1 ( x ) + Q n 2 ( x ) + 2 Q n 1 ( x ) Q_n'(x) \; = \; 2xQ_{n-1}'(x) + Q_{n-2}'(x) + 2Q_{n-1}(x) so that Q 0 ( 1 2 ) = 0 Q_0'(\tfrac12) = 0 , Q 1 ( 1 2 ) = 1 Q_1'(\tfrac12) = 1 and Q n ( 1 2 ) = Q n 1 ( 1 2 ) + Q n 2 ( 1 2 ) + 2 Q n 1 ( 1 2 ) = Q n 1 ( 1 2 ) + Q n 2 ( 1 2 ) + L n 1 Q_n'(\tfrac12) \; = \; Q_{n-1}'(\tfrac12) + Q_{n-2}'(\tfrac12) + 2Q_{n-1}(\tfrac12) \; = \; Q_{n-1}'(\tfrac12) + Q_{n-2}'(\tfrac12) + L_{n-1} Since n F n = ( n 1 ) F n 1 + ( n 2 ) F n 2 + L n 1 nF_n \; = \; (n-1)F_{n-1} + (n-2)F_{n-2} + L_{n-1} we deduce that [ Q n ( 1 2 ) n F n ] = [ Q n 1 ( 1 2 ) ( n 1 ) F n 1 ] + [ Q n 2 ( 1 2 ) ( n 2 ) F n 2 ] \big[Q_n'(\tfrac12) - nF_n\big] \; = \; \big[Q_{n-1}'(\tfrac12) - (n-1)F_{n-1}\big] + \big[Q_{n-2}'(\tfrac12) - (n-2)F_{n-2}\big] and since Q n ( 1 2 ) n F n = 0 Q_n'(\tfrac12) - nF_n = 0 when n = 0 n = 0 and 1 1 , we deduce that Q n ( 1 2 ) = n F n n 0 . Q_n'(\tfrac12) \; = \; nF_n \hspace{2cm} n \ge 0 \;. Thus S = 2017 F 2017 S = 2017F_{2017} and T = 17 F 17 T = 17F_{17} , and hence the fractional part of S T \tfrac{S}{T} is 4142 27149 \tfrac{4142}{27149} , making the answer 4142 \boxed{4142} .

This approach seemed simpler than considering the Chebyshev polynomials P n ( x ) P_n(x) trigonometrically.

I got those formulas for S S and T T but wasn't sure if there was a nice way to compute S S mod T . T. Did you just generate the sequence mod 17 F 17 17 F_{17} on a computer?

Patrick Corn - 3 years, 6 months ago

Log in to reply

I did it by computer originally but, since you ask...

F 17 = 1597 F_{17} = 1597 is (prime and) coprime to 17 17 .

Since F N + 36 F N ( m o d 17 ) F_{N + 36} \equiv F_N \pmod{17} , we deduce that F 2017 F 1 ( m o d 17 ) F_{2017} \equiv F_1 \pmod{17} , and hence 2017 F 2017 11 ( m o d 17 ) 2017F_{2017} \equiv 11 \pmod{17} .

Since F m + n 1 = F m 1 F n 1 + F m F n F_{m+n-1} = F_{m-1}F_{n-1} + F_mF_n we have that F N = F 17 F N 18 + F 18 F N 17 F_N = F_{17}F_{N-18} + F_{18}F_{N-17} , and hence F N F 18 F N 17 ( m o d F 17 ) F_N \equiv F_{18}F_{N-17} \pmod{F_{17}} Thus F 2017 F 18 F 2000 F 18 2 F 1983 F 18 118 F 11 ( m o d F 17 ) F_{2017} \equiv F_{18}F_{2000} \equiv F_{18}^2F_{1983} \equiv \cdots \equiv F_{18}^{118}F_{11} \pmod{F_{17}} Since F n + 1 F n 1 F n 2 = ( 1 ) n F_{n+1}F_{n-1} - F_n^2 = (-1)^n we see that F 18 2 1 ( m o d F 17 ) F_{18}^2 \equiv -1 \pmod{F_{17}} , and hence 2017 F 2017 2017 F 11 948 ( m o d F 17 ) 2017F_{2017} \equiv -2017 F_{11} \equiv 948 \pmod{F_{17}}

This last calculation is "small enough" to be done manually. Solving the appropriate Chinese Remainder equations, we have 2017 F 2017 4142 ( m o d 17 F 17 ) 2017F_{2017} \equiv 4142 \pmod{17F_{17}} as required.

Mark Hennings - 3 years, 6 months ago

Log in to reply

Nice, I did what you did on the mod 17 part but I missed the nice argument for mod F 17 . F_{17}.

Patrick Corn - 3 years, 6 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...