Re: Can someone explain this proof, please?

victor_meldrew_666@xxxxxxxxxxx wrote:

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}.
Show that all a_i and b_j are 0 or 1.

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}.

I was mulling over this proof,
and I don't follow your argument after all.

You say that either a_i b_{j-i} = 1 for some i < j,
or else a_i b_{j-i} = 0 for all i < j.
Why is this so?
Why could we not have a_i b_{j-i} = 1/2 ?

--
Timothy Murphy
e-mail (<80k only): tim /at/ birdsnest.maths.tcd.ie
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
.

Relevant Pages