Maths Olympiad Prep

Library / /59 of 299

Algebra Difficulty 5.9 AIME, harder Prove it Iran

Consider the sequence (an)nN(a_n)_{n \in \mathbb{N}} where a1=2a_1 = 2 and for n1n \ge 1 we have
an+1=(1+1n)nan. a_{n+1} = \left(1 + \frac{1}{n}\right)^n a_n.

Prove that there are infinitely many nn such that 1n+1anan1a1\frac{1}{n+1}a_n a_{n-1} \dots a_1 is a perfect square of a natural number.

Solutions — 2

Solution 1

By induction, we prove an=2nnn!a_n = \frac{2n^n}{n!}. The base is clear, if the hypothesis holds true for nn, we have
an+1=(1+1n)nan=2(n+1n)nnnn!=2(n+1)nn!=2(n+1)n+1(n+1)!, a_{n+1} = \left(1 + \frac{1}{n}\right)^n a_n = 2 \cdot \left(\frac{n+1}{n}\right)^n \frac{n^n}{n!} = 2 \cdot \frac{(n+1)^n}{n!} = 2 \cdot \frac{(n+1)^{n+1}}{(n+1)!},
now we have:
anan1a1n+1=2nn+1nn(n1)n12211n!(n1)!2!1!=2nn+1n(n1)1!2!n(n1)(nk1)k!n!n!=2nn+1(n0)(n1)(nn1)(nn), \begin{aligned} \frac{a_n a_{n-1} \cdots a_1}{n+1} &= \frac{2^n}{n+1} \frac{n^n \cdot (n-1)^{n-1} \cdots 2^2 1^1}{n! (n-1)! \cdots 2! 1!} \\ &= \frac{2^n}{n+1} \cdot \frac{n(n-1)}{1! \cdot 2!} \cdots \frac{n(n-1) \cdots (n-k-1)}{k!} \cdots \frac{n!}{n!} \\ &= \frac{2^n}{n+1} \binom{n}{0} \binom{n}{1} \cdots \binom{n}{n-1} \binom{n}{n}, \end{aligned}
note that if nn is odd, then
(n0)(n1)(nn1)(nn)=(n0)(n1)(nn12), \binom{n}{0} \binom{n}{1} \cdots \binom{n}{n-1} \binom{n}{n} = \binom{n}{0} \binom{n}{1} \cdots \binom{n}{\frac{n-1}{2}},
is a perfect square. So it is enough to choose an odd nn such that 2nn+1\frac{2^n}{n+1} is a perfect square. For this, we set n=2k1n = 2^k - 1 for an odd kk, then 2nn+1=22kk1\frac{2^n}{n+1} = 2^{2^k-k-1} is a perfect square as desired.

Solution 2

As in the first solution, we have
anan1a1n+1=2nn+1nn(n1)n12211n!(n1)!2!1!=2nn+1An \frac{a_n a_{n-1} \cdots a_1}{n+1} = \frac{2^n}{n+1} \frac{n^n \cdot (n-1)^{n-1} \cdots 2^2 1^1}{n! (n-1)! \cdots 2! 1!} = \frac{2^n}{n+1} A_n
Each natural number 1in1 \le i \le n is repeated ni+1n-i+1 times in the denominator of AnA_n. In the numerator of AnA_n ii appears with the power ii so we can write
An=i2in1 A_n = \prod i^{2i-n-1}
which means that if nn is odd and AnA_n is natural then it is a perfect square. So it is enough to prove that for infinitely many odd nn, AnA_n is a natural number. Assume that νp(n)=k\nu_p(n) = k, then we have
νp(A)=j=1k2pj(1+2++npj)(n+1)j=1kknpj \nu_p(A) = \sum_{j=1}^{k} 2p^j(1 + 2 + \cdots + \lfloor \frac{n}{p^j} \rfloor) - (n+1) \sum_{j=1}^{k} k \lfloor \frac{n}{p^j} \rfloor
We want to show that νp(A)\nu_p(A) is non-negative. For 1jK1 \le j \le K we have to show that
2pj(1+2++npj)(n+1)npj    pjnpj(npj+1)(n+1)npj    pj(npj+1)(n+1) \begin{align*} 2p^j(1 + 2 + \cdots + \lfloor \frac{n}{p^j} \rfloor) &\ge (n+1)\lfloor \frac{n}{p^j} \rfloor \\ \iff p^j \lfloor \frac{n}{p^j} \rfloor (\lfloor \frac{n}{p^j} \rfloor + 1) &\ge (n+1) \frac{n}{p^j} \\ \iff p^j (\lfloor \frac{n}{p^j} \rfloor + 1) &\ge (n+1) \end{align*}
By division algorithm, n=pjq+rn = p^j q + r for 0r<pj0 \le r < p^j. Hence we have to show that pj(q+1)pjq+r+1pjr+1p^j(q+1) \ge p^j q + r + 1 \Leftrightarrow p^j \ge r + 1 which is clear. The rest of the proof would be analogous to the first solution. ■

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.