1. ## solving inequations

Hello everyone

There are 2n inequations:

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

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

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

Proof that

(3) $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 $(1)_i < (1)_j \ \mbox{if }i < j$, but $a_j \in \mathbb{R}$ and therefor $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:

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

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

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

Proof that

(3) $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 $(1)_i < (1)_j \ \mbox{if }i < j$, but $a_j \in \mathbb{R}$ and therefor $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 $n^{th}$ term of the Fibonacci sequence is $u_n$, then you can prove that
$a_1 +...+a_n+b_1+...+b_n \leq \frac{2u_{2n}-1}{u_{2n}}<2$

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

$a_1+b_1 \leq1$

$a_2+b_1\leq1$

$a_1+a_2+b_2\leq1$

$a_3+b_1+b_2\leq1$

$a_1+a_2+a_3+b_3\leq1$

$a_4+b_1+b_2+b_3\leq1$

$...$

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

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

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

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

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

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

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

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

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

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 $u_i$ be the $i^{th}$ term of the Fibonacci sequence. So:

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

LEMMA 1

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

PROOF

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

Then $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 $P(n) \implies P(n+1)$

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

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

LEMMA 2

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

PROOF

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

Then $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 $P(n) \implies P(n+1)$

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

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

GIVEN

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

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

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

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

TO PROVE

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

PROOF

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

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

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

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

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

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

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

$\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)$

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

Now consider the coefficient of $a_i$:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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

$\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.

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!)

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