Hi,
Here is my problem:

$\sum _{i=1}^{1381}{a}_i=a_1+a_2+...+a_{1381}=2$

$\sum _{i=1}^{1380}{a}_i{a}_{i+1}=a_1{a}_2+a_2{a}_3+...+a_{1380}{a}_{1381}=1$

Let $S=\sum _{i=1}^{1381}{a}_i^2=a_1^2+a_2^2+...+a_{1381}^2$

Find the maximum and minimum of $S$.

By squaring $\sum _{i=1}^{1381}{a}_i$, I've proved that the maximum of $S$ is 2, and it happens when $a_1=a_2=1$, $a_3=a_4=...=a_{1381}=0$.

Using Cauchy inequality, I've also proved that the minimum of $S$, is more than 1. I guess it's 1.5.
Can anybody help me solving this problem?
Abbas.

I don't have an answer (yet), but I wonder if the way to tackle it is to focus on the fact that if the sum of the terms is 2, the sum of products of adjacent terms cannot exceed 1 (I think). By imposing 1 as an actual constraint appears to be limiting severly the range of values that the a's can take.

If we can prove that (for example) the only values that the a's could take were:

i) Two adjacent 1's and zeros everywhere else

or

ii) 0.5,1,0.5 as adjacent terms and zeros everywhere else

then the result follows (i.e. that the minimum value of the sum of squares is 1.5, which appears to be the case).

Andre

Well that sounds like a fair idea, but note that if n=3 rather than n=1381 then we have:

a+b+c=2
ab+bc=1

This is the same as:

b=1
a+c=1

So there are lots of solutions (although 1.5 is minimum). Why do you think minimum is 1.5, I have only checked n=3 case?

Ian

a+b+c+d = 2 => d = 2-a-b-c
ab+bc+cd = 1 => ab+bc+c(2-a-b-c) = 1 => ab-ac = c² -2c+1
So,
a(b-c) = (c-1)² > = 0
If a > 0 then b > = c.
Using a similiar work, we'll have:
If d > 0 then c > = b.
Hence if a,d > 0, then b = c = 1 which means a = d = 0 ! So a or d must be 0.
Maybe one can find a way to prove this using induction:
If such a₁ to a₁₃₈₁ exist, only 3 adjacent terms can be positive.
Abbas.

We start by posing the question that I suggested above:

what is the maximum value of

$F(\{a_i\})=\sum _1^{1380}{a}_i{a}_{i+1}$

given the additional constraint that the $a_i$ are non-negative?

We first observe that $F$ is bounded - it can't exceed 1380*4 for example.

We use lagrange multipliers to find the min/max/stationary points of $F$ by constructing

$H=F-\lambda g$

Then all partial derivatives with respect to $a_i$ are zero, so we must have:

(1) $g=0$

(2) $\mathrm{dH}/{\mathrm{da}}_1=a_2-\lambda =0$

(3) $\mathrm{dH}/{\mathrm{da}}_2=(a_1+a_3)-\lambda =0$

(4) $\mathrm{dH}/{\mathrm{da}}_3=(a_2+a_4)-\lambda =0$

...

(1382) $\mathrm{dH}/{\mathrm{da}}_{1381}=a_{1380}-\lambda =0$

(2) and (4) tell us that $a_4=0$, therefore the solution that minimises $F$ has at least 1 zero.

These zeros may be to the left, the right but not in between the nonzero terms. For if the latter were the case, we could construct a larger $F$ by removing the intervening zeros and putting them at one end.

Therefore, the $a_i$'s that maximise $F$ are those that maximise $F$ but with only 1380 terms, plus a zero on one or the other end.

We can repeat the argument for the case with 1380 terms and so on. The argument fails when either we have 2 or 3 $a_i$'s.

With 3 terms, we have

$g(\{a_i\})=(a_1+a_2+a_3)-2=0$

$F(\{a_i\})=a_1{a}_2+a_2{a}_3$

$H=F-\lambda g$

so again using lagrange multipliers:

(1) $g=0$

(2) $\mathrm{dH}/{\mathrm{da}}_1=a_2-\lambda =0$

(3) $\mathrm{dH}/{\mathrm{da}}_2=(a_1+a_3)-\lambda =0$

(4) $\mathrm{dH}/{\mathrm{da}}_3=a_2-\lambda =0$

So

$a_1=0.5+\delta$

$a_2=1$

$a_3=0.5-\delta$

for some $\delta$.

With 2 terms, we have

$g(\{a_i\})=(a_1+a_2)-2=0$

$F(\{a_i\})=a_1{a}_2$

$H=F-\lambda g$

so again using lagrange multipliers:

(1) $g=0$

(2) $\mathrm{dH}/{\mathrm{da}}_1=a_2-\lambda =0$

(3) $\mathrm{dH}/{\mathrm{da}}_3=a_2-\lambda =0$

So $a_1=1$

$a_2=1$

We have found the solutions that maximise $F$. The maximum is indeed 1. Now Abbas' problem specified that $F=1$. Therefore we know what the possible values of $a_i$ are.

Now with 3 nonzero terms, the minimum sum of squares is 1.5, the maximum is 2 (when $\delta =0$).

With 2 nonzero terms, the sum of squares is 2.
Thus the minimum sum of squares is 1.5 and the maximum is 2.

Andre

Thanks Andre!
Please tell me about Lagrange multiplier, and partial derivative.
Abbas.

An unfortunate property of this proof is that it has to rely on these fairly advanced concepts. I feel sure a more elementary solution must exist - I just can't find it.

Would anyone care to opine on whether the proof is correct? Ian?

As for partial derivatives, are you familiar with differentiation? The idea there is (given a function of x, F(x)), we compute dF/dx - the ratio of the change in F to a small change in x (a terse description but hopefully you've seen it before).

What, though, if F were a function of two variables. E.g. if F(x,y)=x² y² ? If we compute the ratio of the change in F to a small change in x keeping y constant then we are said to be taking the "partial derivative of F with respect to x". Similarly, if we compute the ratio of the change in F to a small change in y keeping x constant then we are said to be taking the "partial derivative of F with respect to y". In our example, the first partial derivative is 2xy² and the second partial derivative is 2x² y.

$(\mathrm{dF}/\mathrm{dx})\delta x+(\mathrm{dF}/\mathrm{dy})\delta y$

This is analagous to the first term of a Taylor expansion for functions of a single variable.

[as a complete aside, and unrelated to this post, I cannot resist pointing out that even for small $\delta x$, it is not correct to ignore higher derivatives if $x$ is stochastic (random). This issue occurs all the time in the world of financial mathematics]

Now we come to Lagrange multipliers.

If we have a function of a single variable, $Q(x)$, we can locate max/min/stationary points by solving $\mathrm{dQ}/\mathrm{dx}=0$. If $Q$ was a function of 2 variables, $Q(x,y)$, we can do the same by simultaneously solving $\mathrm{dQ}/\mathrm{dx}=0$; $\mathrm{dQ}/\mathrm{dy}=0$ (both partial derivatives).

What, though, if we had to maximise $Q(x,y)$ subject to a constraint on $(x,y)$, like $g(x,y)=0$?

If you think about $Q$ as being represented graphically as a series of contours (each representing different values of $Q$), and the constraint $g=0$ being another contour, then we are looking for the point at which both contours touch but do not cross.

How do we represent this intuition mathematically?

Well if

$g(x,y)=0$

then for a small move in $x$, $y$ for which $g=0$ still holds, we must have

$(\mathrm{dg}/\mathrm{dx})\delta x+(\mathrm{dg}/\mathrm{dy})\delta y=0$

We can interpret this equation as being the scalar product of 2 vectors: $(\mathrm{dg}/\mathrm{dx},\mathrm{dg}/\mathrm{dy})$ and $(\delta x,\delta y)$. The fact that the result is zero means that they are perpendicular. Now $(\delta x,\delta y)$ runs along the contour, so $(\mathrm{dg}/\mathrm{dx},\mathrm{dg}/\mathrm{dy})$ must be perpendicular to the contour.

So much for the constraint. What about $Q$? Well we agreed that at our max/min/stationary point, $g=0$ touches but does not cross a contour of $Q$. So at this point, $(\mathrm{dQ}/\mathrm{dx})\delta x+(\mathrm{dQ}/\mathrm{dy})\delta y=0$ as well. The conclusion is that $(\mathrm{dQ}/\mathrm{dx},\mathrm{dQ}/\mathrm{dy})$ must be a vector parallel to $(\mathrm{dg}/\mathrm{dx},\mathrm{dg}/\mathrm{dy})$, in other words, there exists a $\lambda$ (the lagrange multiplier) such that

$d(Q+\lambda g)/\mathrm{dx}=d(Q+\lambda g)/\mathrm{dy}=0$

But this condition is just the stationary point of $Q+\lambda g$ with no constraints!

The recipe for this method is therefore as follows:

i) Write your constraint as $g(x,y)=0$

ii) Write the function to maximise as $F(x,y)$

iii) Construct $G(x,y)=F(x,y)-\lambda g(x,y)$

iv) simultaneously solve:

$g=0$

$\mathrm{dG}/\mathrm{dx}=0$

$\mathrm{dG}/\mathrm{dy}=0$

And thus you can solve for $x$, $y$ and $\lambda$
The method extends to as many independent variables as you wish.

Let me know if you want some examples.

Andre

Thanks Andre,
I understand your solution now.
But isn't there any more straight way?
Abbas.

My friend proved the first part without Lagrange Multipliers. i.e. if

a₁ + .. + a_n =2 (n > =3)

then

a₁ a₂ + .. + a_n-1 a_n < =1 (#)

with equality only if all but 2 or 3 of the a_i s are non-zero.

To do this he drew a box and grid inside with a₂ , a₂ +a₄ , a₂ +a₄ +a₆ ,... (evens) along the bottom and odds up the side. He then shaded in areas corresponding to the sum (#) above- equality iff whole box shaded.

That's a very rough explanation. Needs a picture, I'll do this tomorrow when I have more time. Completely based on Andre's answer.

Ian

This idea was courtesy of my friend Ed Crane.

Andre solved the problem well and Ed proved the first part as I mentioned 2 messages ago. Let,

x=a₁ +a₃ +... (odds)
y=a₂ +a₄ +... (evens)

Then x+y=2 and a₁ a₂ +..+a_n-1 a_n < = xy < =1. Now, xy is the area of the rectangle drawn below and the shaded regions represent a₁ a₂ +..+a_n-1 a_n (for n=6).



Equality can hold in above inequalities iff we do not get a staircase pattern appearing, i.e. only 3 consecutive non-zero terms.

That's the gist of the idea. Sorry for delay.

Ian

Thanks a lot for your diagram Ian and for telling your friend's idea. It's a very good idea to simplifying Andre's solution. In fact, there is no need to a diagram!

Let
x = a₁ + a₃ + ... + a₁₃₈₁
y = a₂ + a₄ + ... + a₁₃₈₀
Then x + y = 2, so P = a₁ a₂ + a₂ a₃ + ... + a₁₃₈₀ a₁₃₈₁ < = xy < = 1.
To have maximum a₁ a₂ + a₂ a₃ + ... + a₁₃₈₀ a₁₃₈₁ , we must have:

P = xy = P
+ a₁ (a₄ + a₆ + ... + a₁₃₈₀ )
+ a₃ (a₆ + a₈ + ... + a₁₃₈₀ )
+ ...
+ a₁₃₈₁ (a₂ + ... + a₁₃₇₈ )

a₁ (a₄ + a₆ + ... + a₁₃₈₀ ) is zero so either a₁ or (a₄ + a₆ + ... + a₁₃₈₀ ) is zero. If a₁ is zero, we eliminate it and continue with the others. Else, a₁₃₈₁ a₂ is zero. If a₁₃₈₁ is zero, we can continue with others, else a₂ = 0. If we swap a₂ and a₁ , P won't decrease so we can let a₁ = 0 and continue with others. Using this method several times, we'll understand there can be at most 3 positives in a s. Rest is simple.
Abbas.

Good, well explained. If maths monthly publish a different answer then please tell me!

Ian

I like this proof, Abbas. It seems much more appropriate to the problem than my calculus solution.

Andre