Results 1 to 7 of 7

Math Help - solving inequations

  1. #1
    Senior Member
    Joined
    Nov 2008
    Posts
    461

    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
    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:

     (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.

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

    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: July 31st 2010, 01:06 AM
  2. Inequations
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 31st 2010, 12:16 PM
  3. Inequations
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: March 27th 2010, 06:10 AM
  4. exponential inequations!
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: February 10th 2010, 07:57 AM
  5. Replies: 3
    Last Post: October 11th 2006, 09:15 PM

Search Tags


/mathhelpforum @mathhelpforum