Re: Can someone explain this proof, please?

Timothy Murphy wrote:
Problem B1 (supposedly "easy" or even "trivial")
at the IMC (International Maths Competition) in 2001, in Prague, reads:

A URL

http://www.imc-math.org.uk/imc2001/prob_sol2.pdf

would have been useful to the reader.

a_i and b_j are non-negative reals such that

(a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1} + x^n)
(b_0 + b_1x + b_2x^2 + ... + b_{m-1}x^{m-1} + x^m)
= 1 + x + x^2 + ... + x^{m+n}.

You have changed their r and s into n and m: later you use r and s :-(

Show that all a_i and b_j are 0 or 1.

The solution offered reads (in toto):

Solution. Multiply the left hand side polynomials. We obtain the
following
equalities:
a0 b0 = 1, a0 b1 + a1 b0 = 1, . . .
Among them one can find equations
a0 + a1 bs-1 + a2 bs-2 + . . . = 1
and
b0 + b1 ar-1 + b2 ar-2 + . . . = 1.
From these equations it follows that a0 , b0 1.

Rather a_0, b_0 <= 1

Taking into account
that
a0 b0 = 1 we can see that a0 = b0 = 1.
Now looking at the following equations we notice that all a's must be
less
than or equal to 1. The same statement holds for the b's.

There are no "following equations". This is quite easy: comparing
coefficients of x^{i+m} gives
1 = a_i + nonnegative terms
so that a_i <= 1.

It follows from
a0 b1 + a1 b0 = 1 that one of the numbers a1 , b1 equals 0 while the other
one must
be 1. Follow by induction.

That last sentence is illiterate.

It certainly does not follow from a_0 b_1 + a_1 b_0 = b_1 + a_1
(and the nonnegativity of a_1 and b_1) that one of a_1 and b_1 is zero.

There is an inductive proof. Take as induction hypothesis:
H_j: a_j = a_{n-j} in {0,1} and b_j = b_{n-j} in {0,1}.

Certainly H_0 is true. Assume j > 0 and H_i is true
whenever i < j.

If there is 0 < i < j with a_i b_{j-i} = 1 then by the x^j term
1 = a_j + b_j + a_i b_{j-1} + nonnegative terms
so that a_j = b_j = 0.
Also a_{n-i} b_{m-j+i} = 1 and similarly a_{n-i} = b_{m-j+1} = 0.

Otherwise (due to H_i and H_{j-i})
a_j b_{j-i} = 0 for all 0 < i < j which leads to
a_j + b_j = 1. In this case also a_{n-j} + b_{m-j} = 1.
If a_j > 0 then considering the x^m term gives
1 = 1 + a_j b_{m-j} + nonnegative terms
leading to b_{m-j} = 0. Similarly b_j > 0 implies a_{n-j} = 0.
As a_{n-j} + b_{m-j} = 1 at least one of a_j and b_j vanishes,
so one is 0 and the other 1. Similarly one of a_{n-j} and b_{n-j}
is 0 and the other 1. But a_j = 1 implies b_{m-j} = 0 implies
a_{n-j} = 1. Also b_j = 1 implies b_{n-j} = 1. We deduce
that always a_j = a_{n-j} and b_j = b_{m-j}.

Victor Meldrew

.