# Thread: solving inequations

1. ## solving inequations

Hello everyone

There are 2n inequations:

$\displaystyle (1)_i (a_1 + ... + a_i) + b_i \le 1, i = 1, ... , n$

$\displaystyle (2)_i (b_1 + ... + b_i) + a_{i+1} \le 1, i = 1,...,n$ and $\displaystyle a_{n+1} = 0,$

where $\displaystyle a_1 ,...,a_n, b_1 ,...,b_n \in \mathbb{R}$

Proof that

(3) $\displaystyle a_1 + ... + a_n + b_1 + ... + b_n < 2$

i could really use a hand here, I dont know how to solve it

I thought $\displaystyle (1)_i < (1)_j \ \mbox{if }i < j$, but $\displaystyle a_j \in \mathbb{R}$ and therefor $\displaystyle a_j < 0$ is possible.

Help is much appreciated

Thank you,
Rapha

2. ## Inequalities and Fibonacci sequence

Hello Rapha-

Originally Posted by Rapha
Hello everyone

There are 2n inequations:

$\displaystyle (1)_i (a_1 + ... + a_i) + b_i \le 1, i = 1, ... , n$

$\displaystyle (2)_i (b_1 + ... + b_i) + a_{i+1} \le 1, i = 1,...,n$ and $\displaystyle a_{n+1} = 0,$

where $\displaystyle a_1 ,...,a_n, b_1 ,...,b_n \in \mathbb{R}$

Proof that

(3) $\displaystyle a_1 + ... + a_n + b_1 + ... + b_n < 2$

i could really use a hand here, I dont know how to solve it

I thought $\displaystyle (1)_i < (1)_j \ \mbox{if }i < j$, but $\displaystyle a_j \in \mathbb{R}$ and therefor $\displaystyle a_j < 0$ is possible.

Help is much appreciated

Thank you,
Rapha
I haven't got a complete proof in an elegant form, but I think it's all to do with the terms of the Fibonacci sequence. If the $\displaystyle n^{th}$ term of the Fibonacci sequence is $\displaystyle u_n$, then you can prove that
$\displaystyle a_1 +...+a_n+b_1+...+b_n \leq \frac{2u_{2n}-1}{u_{2n}}<2$

Write the inequalities $\displaystyle (1)_i$ and $\displaystyle (2)_i$ on alternate lines, and, in the case of the $\displaystyle (2)_i$, write the $\displaystyle a$ term before the $\displaystyle b$ term:

$\displaystyle a_1+b_1 \leq1$

$\displaystyle a_2+b_1\leq1$

$\displaystyle a_1+a_2+b_2\leq1$

$\displaystyle a_3+b_1+b_2\leq1$

$\displaystyle a_1+a_2+a_3+b_3\leq1$

$\displaystyle a_4+b_1+b_2+b_3\leq1$

$\displaystyle ...$

$\displaystyle a_1+a_2+...+a_n+b_n\leq1$

$\displaystyle b_1+b_2+...+b_n\leq1$
(Note that this final inequality does not have the term in a, because $\displaystyle a_{n+1}=0$

We now have 2n inequalities. Then, for $\displaystyle i=1$ to $\displaystyle 2n-1$ multiply the $\displaystyle i^{th}$ inequality by the $\displaystyle i^{th}$ term in the Fibonacci sequence, $\displaystyle u_i$, and the final inequality by $\displaystyle u_{2n-2}$. Now add all the resulting inequalites. You'll then find that all the coefficients of the $\displaystyle a$'s and $\displaystyle b$'s are equal to $\displaystyle u_{2n}$, and the RHS is $\displaystyle 2u_{2n}-1$.

For instance, when n = 2, multiply the inequalities by 1, 1, 2 and 1 respectively, and add. The result is

$\displaystyle 3(a_1+a_2+b_1+b_2)\leq5$

and when n = 3, multiply by 1, 1, 2, 3, 5, 3 to get

$\displaystyle 8(a_1+a_2+a_3+b_1+b_2+b_3)\leq15$

Dividing both sides by $\displaystyle u_{2n}$ completes the proof.

I hope you can improve on this. I'd like to see a more formal proof.

Grandad

3. Hello Grandad.

Thank you so much, your answer is great.

Best regards,
Rapha

4. ## Inequalities: Formal Proof

Hello Rapha -

Thanks for your kind comment. I found this a most interesting problem, and I have now written out a formal proof. I assume that you have come up with one as well, but here's mine, if you're interested:

First, two lemmas relating to the Fibonacci sequence.

Let $\displaystyle u_i$ be the $\displaystyle i^{th}$ term of the Fibonacci sequence. So:

$\displaystyle u_i =u_{i-1}+u_{i-2}$ and $\displaystyle u_1 = u_2=1$

LEMMA 1

$\displaystyle \sum_{i=1}^nu_{2i-1}=u_{2n}$

PROOF

Define the propositional function $\displaystyle P(n) \equiv S_n=\sum_{i=1}^nu_{2i-1}=u_{2n}$

Then $\displaystyle P(n) \implies S_{n+1}=S_n+u_{2n+1}=u_{2n}+u_{2n+1}=u_{2(n+1)}$ from the recurrence relation for the sequence.

So $\displaystyle P(n) \implies P(n+1)$

Now $\displaystyle P(1)\equiv S_1 = u_1=u_2$, which is true.

Hence $\displaystyle P(n)\quad \forall n \in \mathbb{N}$

LEMMA 2

$\displaystyle \sum_{i=1}^nu_{2i}=u_{2n+1}-1$

PROOF

Define the propositional function $\displaystyle P(n) \equiv S_n=\sum_{i=1}^nu_{2i}=u_{2n+1}-1$

Then $\displaystyle P(n) \implies S_{n+1}=S_n+u_{2n+2}=u_{2n+1}+u_{2n+2}-1=u_{2(n+1)+1}-1$ from the recurrence relation for the sequence.

So $\displaystyle P(n) \implies P(n+1)$

Now $\displaystyle P(1)\equiv S_1 = u_2=u_3-1$, which is true.

Hence $\displaystyle P(n)\quad \forall n \in \mathbb{N}$

GIVEN

$\displaystyle (1)_i\quad (a_1 + ... + a_i) + b_i \le 1, i = 1, ... , n$

$\displaystyle (2)_i\quad (b_1 + ... + b_i) + a_{i+1} \le 1, i = 1,...,n-1$

$\displaystyle (3)\quad (b_1 + ... + b_n)\le 1$

where $\displaystyle a_1 ,...,a_n, b_1 ,...,b_n \in \mathbb{R}$

TO PROVE

$\displaystyle a_1 + ... + a_n + b_1 + ... + b_n < 2$

PROOF

For $\displaystyle i =1\text{ to }n$, multiply each $\displaystyle (1)_i$ by $\displaystyle u_{2i-1}$:

$\displaystyle u_{2i-1}(a_1+...+a_i)+u_{2i-1}b_i \le u_{2i-1}\quad (4)$

For $\displaystyle i=1 \text{ to }n-1$, multiply each $\displaystyle (2)_i$ by $\displaystyle u_{2i}$:

$\displaystyle u_{2i}(b_1+...+b_i)+u_{2i}a_{i+1} \le u_{2i} \quad (5)$

Multiply $\displaystyle (3)$ by $\displaystyle u_{2n-2}$:

$\displaystyle u_{2n-2}(b_1+...+b_n) \le u_{2n-2} \quad (6)$

Add $\displaystyle (4)$, $\displaystyle (5)$ and $\displaystyle (6)$:

$\displaystyle \sum_{i=1}^n u_{2i-1}(a_1+...+a_i) + \sum_{i=1}^nu_{2i-1}b_i+\sum_{i=1}^{n-1}u_{2i}(b_1+...+b_i)+\sum_{i=1}^{n-1}u_{2i}a_{i+1}+u_{2n-2}(b_1+...+b_n)$

$\displaystyle \le \sum_{i=1}^nu_{2i-1}+\sum_{i=1}^{n-1}u_{2i}+u_{2n-2} \quad (7)$

Now consider the coefficient of $\displaystyle a_i$:

For $\displaystyle i=1$, coefficient of $\displaystyle a_i=\sum_{i=1}^nu_{2i-1}=u_{2n}$, from LEMMA 1

For $\displaystyle 2 \le i \le n$, coefficient of $\displaystyle a_i=\sum_{j=i}^nu_{2j-1}+u_{2(i-1)}$

$\displaystyle =\sum_{j=i}^nu_{2j-1}+\sum_{j=1}^{i-1}u_{2j-1}$, from LEMMA 1

$\displaystyle =\sum_{j=1}^n u_{2j-1}$

$\displaystyle =u_{2n}$, from LEMMA 1

Now consider the coefficient of $\displaystyle b_i$ in $\displaystyle (7)$:

For $\displaystyle 1 \le i\le n-1$, coefficient of $\displaystyle b_i = u_{2i-1}+\sum_{j=i}^{n-1}u_{2j}+u_{2n-2}$

$\displaystyle =1+\sum_{j=i}^{i-1}u_{2j}+\sum_{j=i}^{n-1}u_{2j}+u_{2n-2}$, from LEMMA 2

$\displaystyle =1+\sum_{j=1}^{n-1}u_{2j}+u_{2n-2}$

$\displaystyle =1+u_{2n-1}-1+u_{2n-2}$, from LEMMA 2

$\displaystyle =u_{2n-2}+u_{2n-1}$

$\displaystyle =u_{2n}$, from the recurrence relation.

For $\displaystyle i=n$, the coefficient of $\displaystyle b_i = u_{2n-1}+u_{2n-2}=u_{2n}$, from the recurrence relation

Finally, using LEMMA 1 and LEMMA 2 on the RHS, $\displaystyle (7)$ becomes:

$\displaystyle u_{2n}(a_1+...+a_n+b_1+...+b_n)\le u_{2n}+u_{2n-1}-1+u_{2n-2}=2u_{2n}-1$, from the recurrence relation

$\displaystyle \implies a_1+...+a_n+b_1+...+b_n \le \frac{2u_{2n}-1}{u_{2n}} < 2$

QED

I would be interested to see if you have found any significant way of shortening this proof.

Grandad

5. Hi

I found this a most interesting problem, and I have now written out a formal proof. I assume that you have come up with one as well,
To tell the truth I tried… and failed…
but here's mine, if you're interested:
Of course I’m interested, I would love to see it.
...
...
QED
Wow. That's awesome. I really appreciate your formal proof. Thanks for all the help.
I would be interested to see if you have found any significant way of shortening this proof.
I did not, but in like three months my teacher will make a proposal for a solution.
Kind regards,
Rapha

6. ## Thanks

Hi Rapha -

Thanks for your comments. It will be interesting to see what your teacher comes up with! By the way, what level is your course? (This was certainly a fairly tricky question!)

Grandad

7. Hello Grandad.

Originally Posted by Grandad
It will be interesting to see what your teacher comes up with!
I'm going to post it here.

Originally Posted by Grandad
By the way, what level is your course?
It is my third semester at university.
The course is called: "linear programming".

Originally Posted by Grandad
(This was certainly a fairly tricky question!)
It sure was.

Rapha