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.

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.

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.