Maths Olympiad Prep

Library / /491 of 520

Algebra Difficulty 7.7 National olympiad, round 2 Prove it

Sequences (an)n=0(a_n)_{n=0}^{\infty} and (bn)n=0(b_n)_{n=0}^{\infty} are defined with recurrent relations :
a0=0,      a1=1,        an+1=2018nan+an1      for       n1a_0=0 , \;\;\; a_1=1, \;\;\;\; a_{n+1}=\frac{2018}{n} a_n+ a_{n-1}\;\;\; \text {for }\;\;\; n\geq 1 and
b0=0,      b1=1,        bn+1=2020nbn+bn1      for       n1b_0=0 , \;\;\; b_1=1, \;\;\;\; b_{n+1}=\frac{2020}{n} b_n+ b_{n-1}\;\;\; \text {for }\;\;\; n\geq 1
Prove that :a10101010=b10091009\frac{a_{1010}}{1010}=\frac{b_{1009}}{1009}

Solution

1. Define the sequences: Let (xn)n>0(x_n)_{n>0} and (yn)n>0(y_n)_{n>0} be sequences defined by xn=annx_n = \frac{a_n}{n} and yn=bnny_n = \frac{b_n}{n} for all n1n \geq 1. We aim to show that x1010=y1009x_{1010} = y_{1009}.

2. Transform the recurrence relations:
- For (an)(a_n), the recurrence relation is an+1=2018nan+an1a_{n+1} = \frac{2018}{n} a_n + a_{n-1}.
- For (bn)(b_n), the recurrence relation is bn+1=2020nbn+bn1b_{n+1} = \frac{2020}{n} b_n + b_{n-1}.

3. Express the generating functions:
- Let T(x)=n=1xnxnT(x) = \sum_{n=1}^{\infty} x_n x^n.
- From the recurrence relation for ana_n, we have:
T(x)1=2018T(x)+x2T(x). T'(x) - 1 = 2018 T(x) + x^2 T'(x).
- Rearrange and solve for T(x)T(x):
T(x)1=2018T(x)+x2T(x)    T(x)(1x2)=2018T(x)+1. T'(x) - 1 = 2018 T(x) + x^2 T'(x) \implies T'(x)(1 - x^2) = 2018 T(x) + 1.
- Let P(x)=T(x)+12018P(x) = T(x) + \frac{1}{2018}, then:
2018P(x)=P(x)(1x2). 2018 P(x) = P'(x)(1 - x^2).

4. Solve the differential equation:
- Similarly, for Q(x)=n=1ynxn+12020Q(x) = \sum_{n=1}^{\infty} y_n x^n + \frac{1}{2020}, we get:
2020Q(x)=Q(x)(1x2). 2020 Q(x) = Q'(x)(1 - x^2).
- Let R(x)R(x) be the solution to R(x)=R(x)(1x2)R(x) = R'(x)(1 - x^2) with R(0)=1R(0) = 1.

5. **Find the general solution for R(x)R(x)**:
- Solve the differential equation:
R(x)R(x)=11x2    R(x)R(x)dx=12(11+x+11x)dx. \frac{R'(x)}{R(x)} = \frac{1}{1 - x^2} \implies \int \frac{R'(x)}{R(x)} \, dx = \frac{1}{2} \int \left( \frac{1}{1 + x} + \frac{1}{1 - x} \right) \, dx.
- Integrate both sides:
log(R(x))=12(log(1+x)log(1x))+c1    R(x)=c2(1+x)1/2(1x)1/2. \log(R(x)) = \frac{1}{2} (\log(1 + x) - \log(1 - x)) + c_1 \implies R(x) = c_2 (1 + x)^{1/2} (1 - x)^{-1/2}.
- Given R(0)=1R(0) = 1, we find c2=1c_2 = 1, so:
R(x)=(1+x)1/2(1x)1/2. R(x) = (1 + x)^{1/2} (1 - x)^{-1/2}.

6. **Express P(x)P(x) and Q(x)Q(x)**:
- We have:
P(x)=R(x)20182018,Q(x)=R(x)20202020. P(x) = \frac{R(x)^{2018}}{2018}, \quad Q(x) = \frac{R(x)^{2020}}{2020}.

7. Find the coefficients:
- For x1010x_{1010}:
x1010=[x1010]P(x)=12018[x1010]((1+x)1009(1x)1009). x_{1010} = [x^{1010}] P(x) = \frac{1}{2018} [x^{1010}] \left( (1 + x)^{1009} (1 - x)^{-1009} \right).
- For y1009y_{1009}:
y1009=[x1009]Q(x)=12020[x1009]((1+x)1010(1x)1010). y_{1009} = [x^{1009}] Q(x) = \frac{1}{2020} [x^{1009}] \left( (1 + x)^{1010} (1 - x)^{-1010} \right).

8. Evaluate the coefficients:
- Using the binomial series expansion:
(1+x)1009(1x)1009=k=01009(1009k)xkk=0(k+10081008)xk. (1 + x)^{1009} (1 - x)^{-1009} = \sum_{k=0}^{1009} \binom{1009}{k} x^k \sum_{k=0}^{\infty} \binom{k + 1008}{1008} x^k.
- Similarly for y1009y_{1009}:
(1+x)1010(1x)1010=k=01010(1010k)xkk=0(k+10091009)xk. (1 + x)^{1010} (1 - x)^{-1010} = \sum_{k=0}^{1010} \binom{1010}{k} x^k \sum_{k=0}^{\infty} \binom{k + 1009}{1009} x^k.

9. Compare the sums:
- We find:
x1010=k=01009(2018k)!2k!(1009k)!(1010k)!, x_{1010} = \sum_{k=0}^{1009} \frac{(2018 - k)!}{2 \cdot k! \cdot (1009 - k)! \cdot (1010 - k)!},
y1009=k=01009(2018k)!2k!(1010k)!(1009k)!. y_{1009} = \sum_{k=0}^{1009} \frac{(2018 - k)!}{2 \cdot k! \cdot (1010 - k)! \cdot (1009 - k)!}.
- Therefore, x1010=y1009x_{1010} = y_{1009}.

The final answer is a10101010=b10091009\boxed{\frac{a_{1010}}{1010} = \frac{b_{1009}}{1009}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.