Maths Olympiad Prep

Library / /250 of 462

Algebra Difficulty 5.9 AIME, harder Prove it Ireland

Prove that 11 is the only positive value of rr for which there is a two-way infinite sequence a(n)a(n) such that
a(n)=1k=0nrka(nk), n=0,±1,±2, a(-n) = 1 - \sum_{k=0}^{n} r^k a(n-k), \ n = 0, \pm 1, \pm 2, \dots
Determine a(n)a(n), n=0,±1,±2,n = 0, \pm1, \pm2, \dots, when r=1r = 1.

Solution

Suppose, for some r>0r > 0, a two-way infinite sequence a(n)a(n) satisfies
a(n)=1k=0nrka(nk),for all nZ.(1) a(-n) = 1 - \sum_{k=0}^{n} r^k a(n-k), \quad \text{for all } n \in \mathbb{Z}. \qquad (1)

For n=0n = 0 this means a(0)=1a(0)a(0) = 1 - a(0), hence a(0)=12a(0) = \frac{1}{2}. For n=±1n = \pm 1 we get
a(1)+a(1)=1r1a(0)and(2) a(1) + a(-1) = 1 - r^{-1}a(0) \quad \text{and} \qquad (2)
a(1)+a(1)=1ra(0).(3) a(-1) + a(1) = 1 - ra(0). \qquad (3)
Combining (2) and (3) gives r1a(0)=ra(0)r^{-1}a(0) = ra(0), whence r2=1r^2 = 1, so that r=1r = 1, as claimed. With r=1r = 1, (1) simplifies to

a(n)=1k=0na(nk),for all nZ. a(-n) = 1 - \sum_{k=0}^{n} a(n-k), \quad \text{for all } n \in \mathbb{Z}.
We rewrite this in two ways, using only n0n \ge 0:
a(n)=1k=0na(k)and(4) a(-n) = 1 - \sum_{k=0}^{n} a(k) \quad \text{and} \qquad (4)
a(n)=1k=0na(k).(5) a(n) = 1 - \sum_{k=0}^{n} a(-k). \qquad (5)

Writing d(n)=a(n)a(n)d(n) = a(n) - a(-n), the difference of (4) and (5) gives
d(n)=k=0nd(k), i.e. k=0n1d(k)=0,for all n1,(6) d(n) = \sum_{k=0}^{n} d(k), \text{ i.e. } \sum_{k=0}^{n-1} d(k) = 0, \quad \text{for all } n \ge 1, \qquad (6)
Clearly, d(0)=a(0)a(0)=0d(0) = a(0) - a(-0) = 0 and so induction and (6) gives d(n)=0d(n) = 0, i.e. a(n)=a(n)a(n) = a(-n) for all n0n \ge 0. Now (5) becomes
a(n)=1k=0na(k),i.e.2a(n)=1k=0n1a(k),for all n0. a(n) = 1 - \sum_{k=0}^{n} a(k), \quad \text{i.e.}\quad 2a(n) = 1 - \sum_{k=0}^{n-1} a(k), \quad \text{for all } n \ge 0.
Replacing 1k=0n2a(k)1 - \sum_{k=0}^{n-2} a(k) in this last expression by 2a(n1)2a(n-1), we obtain
2a(n)=2a(n1)a(n1)=a(n1),for all n1. 2a(n) = 2a(n-1) - a(n-1) = a(n-1), \quad \text{for all } n \ge 1.
Since a(0)=1/2a(0) = 1/2 it now follows by induction that a(n)=1/2n+1a(n) = 1/2^{n+1}, for all n0n \ge 0. Because a(n)=a(n)a(-n) = a(n), we finally obtain

a(n) = 12n+1,for\frac{1}{2^{|n|+1}}, \quad \text{for} all } n Z.\in \mathbb{Z}.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.