Results 1 to 7 of 7

Thread: solving inequations

  1. #1
    Senior Member
    Joined
    Nov 2008
    Posts
    461

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Inequalities and Fibonacci sequence

    Hello Rapha-

    Quote Originally Posted by Rapha View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2008
    Posts
    461
    Hello Grandad.

    Thank you so much, your answer is great.

    Best regards,
    Rapha
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2008
    Posts
    461
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2008
    Posts
    461
    Hello Grandad.

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

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


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


    Rapha
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question about inequations
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Jul 31st 2010, 01:06 AM
  2. Inequations
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Mar 31st 2010, 12:16 PM
  3. Inequations
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Mar 27th 2010, 06:10 AM
  4. exponential inequations!
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: Feb 10th 2010, 07:57 AM
  5. Replies: 3
    Last Post: Oct 11th 2006, 09:15 PM

Search Tags


/mathhelpforum @mathhelpforum