Maths Olympiad Prep

Library / /22 of 23

Algebra Difficulty 7.4 National olympiad, round 2 Prove it Ireland

Given a positive integer mm, a sequence of real numbers a=(a1,a2,a3,...)a = (a_1, a_2, a_3, ...) is called mm-powerful if it satisfies
(k=1nak)m=k=1nakmfor all positive integers n. \left( \sum_{k=1}^{n} a_k \right)^m = \sum_{k=1}^{n} a_k^m \quad \text{for all positive integers } n.

a.
Show that a sequence is 30-powerful if and only if at most one of its terms is non-zero.

b.
Find a sequence none of whose terms is zero but which is 2017-powerful.

Solution

If at most one term in a sequence aa is non-zero, it is immediate that it is mm-powerful for all mNm \in \mathbb{N}. We will see that there are no other 30-powerful sequences (or indeed, mm-powerful for any even mm), but that there are many other sequences that are mm-powerful for all odd mm.

We begin our analysis with a simple lemma.

Lemma. For mNm \in \mathbb{N}, let Pm(x,y)=(x+y)mxmymP_m(x, y) = (x+y)^m - x^m - y^m, x,yRx, y \in \mathbb{R}. Then Pm(x,y)=0P_m(x, y) = 0 whenever xy=0xy = 0. Moreover, PmP_m has no other roots if mm is even, but Pm(x,x)=0P_m(x, -x) = 0 if mm is odd.

Proof. Let p(t)=(1+t)m1tmp(t) = (1+t)^m - 1 - t^m, tRt \in \mathbb{R}. By expansion of (1+t)m(1+t)^m, we see that pp is a polynomial with non-negative coefficients, and so p(t)>0p(t) > 0 for t>0t > 0. Suppose additionally that mm is even. If 1t<0-1 \le t < 0, then (1+t)m10(1+t)^m - 1 \le 0, so p(t)tm<0p(t) \le -t^m < 0. If t<1t < -1, then 0<(1+t)m<tm0 < (1+t)^m < t^m, so p(t)<1<0p(t) < -1 < 0. We conclude that 00 is the only root of pp when mm is even. If xy0xy \ne 0, then Pm(x,y)=xmp(t)P_m(x, y) = x^m p(t), where pp is as above, and t=y/x0t = y/x \ne 0. It follows that Pm(x,y)0P_m(x, y) \ne 0 if mm is even and xy0xy \ne 0:

The statements that Pm(x,y)=0P_m(x, y) = 0 when xy=0xy = 0 (regardless of the parity of mm) and Pm(x,x)=0P_m(x, -x) = 0 when mm is odd, both follow immediately. \square

Fix an arbitrary sequence a=(ak)a = (a_k). For m,nNm, n \in \mathbb{N}, let
S(m,n)=(k=1nak)mk=1nakm, S(m, n) = \left( \sum_{k=1}^{n} a_k \right)^m - \sum_{k=1}^{n} a_k^m,
and let D(m,n)=S(m,n+1)S(m,n)D(m, n) = S(m, n+1) - S(m, n). The condition "a is m-powerful"
says that S(m,n)=0S(m, n) = 0, nNn \in \mathbb{N}, and so we also have D(m,n)=0D(m, n) = 0.

Define xn=an+1x_n = a_{n+1} and yn=k=1naky_n = \sum_{k=1}^{n} a_k. The equation S(m,n)=0S(m, n) = 0 can be written as
ynm=k=1nakm, y_n^m = \sum_{k=1}^{n} a_k^m,
so if this equation holds, then the equation D(m,n)=0D(m, n) = 0 can be written as
(xn+yn)mxnmynm=0. (x_n + y_n)^m - x_n^m - y_n^m = 0.

Suppose now that mm is even and aa is mm-powerful. By the lemma, we conclude that xnyn=0x_n y_n = 0 for all nNn \in \mathbb{N}. We will use these last equations to prove by induction on iNi \in \mathbb{N}, that at most one of the terms a1,...,aia_1, ..., a_i is non-zero; we call this property AiA_i.

A1A_1 is trivially true, so suppose that AiA_i is true for a specific i=nNi = n \in \mathbb{N}. If a1,,ana_1, \dots, a_n are all zero, then An+1A_{n+1} follows immediately, so we may assume that exactly one of these terms is non-zero. But now yn0y_n \ne 0, so the equation xnyn=0x_n y_n = 0 implies that xn=an+1=0x_n = a_{n+1} = 0, and we again deduce An+1A_{n+1}. This finishes the proof that if mm is even, then the mm-powerful sequences are those with at most one non-zero term. Part (a) follows.

The analysis is similar for mm odd, but now PmP_m has other roots in the lemma. By considering these roots, our analysis readily leads us to see that a=((1)n)n=1a = ((-1)^n)_{n=1}^\infty is mm-powerful for every cRc \in \mathbb{R}. Taking any non-zero cc, we get an example with the properties required in (b).

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 and solution reproduced as published; topic and difficulty added by this site.