Maths Olympiad Prep

Library / /469 of 860

Algebra Difficulty 5.2 AIME, harder Find the answer

Let 11xx2x3=i=0anxn\frac{1}{1-x-x^{2}-x^{3}}=\sum_{i=0}^{\infty} a_{n} x^{n}, for what positive integers nn does an1=n2a_{n-1}=n^{2} ?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Multiplying both sides by 1xx2x31-x-x^{2}-x^{3} the right hand side becomes a0+(a1a0)x+(a2a1a0)x2+a_{0}+\left(a_{1}-a_{0}\right) x+\left(a_{2}-a_{1}-a_{0}\right) x^{2}+\ldots, and setting coefficients of xnx^{n} equal to each other we find that a0=1,a1=1,a2=2a_{0}=1, a_{1}=1, a_{2}=2, and an=an1+an2+an3a_{n}=a_{n-1}+a_{n-2}+a_{n-3} for n3n \geq 3. Thus the sequence of ana_{n} 's starts 1,1,2,4,7,13,24,44,81,149,1,1,2,4,7,13,24,44,81,149, \ldots So we now see that a0=12a_{0}=1^{2} and a8=92a_{8}=9^{2}. What makes it impossible for this to happen again is that the sequence is growing exponentially. It will suffice to show that an>1.5na_{n}>1.5^{n} for n>2n>2, since n2/(n1)2<1.5n^{2} /(n-1)^{2}<1.5 for n6n \geq 6, thus when an1a_{n-1} exceeds n2n^{2} at n=10n=10 there can be no more solutions to an1=n2a_{n-1}=n^{2}. Observe that an>1.5an1a_{n}>1.5 a_{n-1} for n=3,4,5n=3,4,5. By way of induction, assume it for n2n-2, n1n-1, and nn, then an+1=an+an1+an2>1.5n+1.5n1+1.5n2=1.5n2(1+1.5+1.52)>1.5n+1a_{n+1}=a_{n}+a_{n-1}+a_{n-2}>1.5^{n}+1.5^{n-1}+1.5^{n-2}=1.5^{n-2}\left(1+1.5+1.5^{2}\right)>1.5^{n+1}. Thus, by induction, an>1.5na_{n}>1.5^{n} for n>2n>2, so the only solutions are 1,9\mathbf{1}, \mathbf{9}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.