Results 1 to 11 of 11
Like Tree5Thanks
  • 1 Post By Jzon758
  • 1 Post By emakarov
  • 1 Post By emakarov
  • 1 Post By Jzon758
  • 1 Post By emakarov

Math Help - How to prove it

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    54

    Question How to prove it

    Hello people,

    I need some advice and help. First of all i am not a mathematician but know a thing or two, here and there. However i have no experience in proving theorems and cases. So if there is anyone patient out there please help. The problem I'm having is as follows:

    I have an array of numbers A[0..n] (an interval to be more precise) and every number A[i] in this interval is associated with a number b such that:

    if A[i] = b then A[i+1] >= b-1


    So what i want to show is that |A[i..i+x]| +A[i+x+1] <= A[i] + A[j] for x<=j and i+A[i] = j holds. ## sorry about this it slipped (A[x] was corrected to A[x+i+1])

    (|A[k..l]| means the length fo an onterval [k..l])

    How would i approach this? what do i need to show first? Aer there more ways to prove the inequality?

    baxy
    Last edited by baxy77bax; July 7th 2012 at 10:15 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jun 2012
    From
    Riverside
    Posts
    9
    Thanks
    2

    Re: How to prove it

    This is for computer science? So I'm not all that familiar with arrays, but what I'm getting from A[i]=b and A[i+1]>=b-1, is that each successive number that the array represents is greater than or equal to the number before. So the array is increasing? Also by length of interval, do you mean the distance between k and l or the distance between A[K] and A[l]?

    So we need to start by assuming the right part x<=j and i+A[i]=j holds. x<=j implies A[x]<=A[j]. If you can show |A[k..l]|<=A[i] you will be done. It probably uses the fact that i+A[i]=j holds as well as the array is increasing. I'm confused as the meaning of length thought. This is an interesting problem.
    Thanks from baxy77bax
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: How to prove it

    Quote Originally Posted by baxy77bax View Post
    I have an array of numbers A[0..n] (an interval to be more precise) and every number A[i] in this interval is associated with a number b
    So, there is another array b[0..n], right?

    Quote Originally Posted by baxy77bax View Post
    such that:

    if A[i] = b then A[i+1] >= b-1
    Does this mean

    If A[i] = b[i] then A[i+1] >= b[i]-1
    If A[i] = b[i] then A[i+1] >= b[i+1]-1

    or something else?

    Also, if b[0..n] is such that A[i] != b[i] for all i, then there is no restriction on the array A, right?

    Quote Originally Posted by baxy77bax View Post
    So what i want to show is that |A[i..i+x]| +A[x] <= A[i] + A[j] for x<=j and i+A[i] = j holds.
    So, |A[i..i+x]| = x-i+1? For a given j, why does i such that i+A[i] = j exist?

    Is there some background to this situation that can provide more intuition?
    Thanks from baxy77bax
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Oct 2008
    Posts
    54

    Re: How to prove it

    Quote Originally Posted by Jzon758 View Post
    This is for computer science?
    yes
    Quote Originally Posted by Jzon758 View Post
    what I'm getting from A[i]=b and A[i+1]>=b-1, is that each successive number that the array represents is greater than or equal to the number before. So the array is increasing?
    The answer is again yes but array in not increasing because the last b values of the array are: A[n-b] = b, A[n-b+1] = b-1 ... A[n] = 0


    Quote Originally Posted by Jzon758 View Post
    Also by length of interval, do you mean the distance between k and l or the distance between A[K] and A[l]?
    I mean the distance between k and l
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    Posts
    54

    Re: How to prove it

    Quote Originally Posted by emakarov View Post
    So, there is another array b[0..n], right?
    Yes
    Quote Originally Posted by emakarov View Post
    Does this mean

    If A[i] = b[i] then A[i+1] >= b[i]-1
    If A[i] = b[i] then A[i+1] >= b[i+1]-1

    or something else?
    It means : If A[i] = b[i] then A[i+1] >= b[i]-1

    Quote Originally Posted by emakarov View Post
    Also, if b[0..n] is such that A[i] != b[i] for all i, then there is no restriction on the array A, right?
    yes
    Quote Originally Posted by emakarov View Post
    So, |A[i..i+x]| = x-i+1?
    yes
    Quote Originally Posted by emakarov View Post
    For a given j, why does i such that i+A[i] = j exist?
    well this i a question i do not understand, so values in b are smaller the n=|A| so why wouldn't i+A[i] = j exist? maybe i confused U by not giving b[i]<n condition
    Quote Originally Posted by emakarov View Post
    Is there some background to this situation that can provide more intuition?
    Well there is no specific background it is just a table for which i an trying to prove its limits
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: How to prove it

    Quote Originally Posted by baxy77bax View Post
    well this i a question i do not understand, so values in b are smaller the n=|A| so why wouldn't i+A[i] = j exist?
    If you have an equation on i, it may have no solutions. For example, it may be that j is odd, but A[i] is even for even i and A[i] is odd for odd i. Then i + A[i] is always even.
    Thanks from baxy77bax
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2008
    Posts
    54

    Re: How to prove it

    Quote Originally Posted by emakarov View Post
    If you have an equation on i, it may have no solutions. For example, it may be that j is odd, but A[i] is even for even i and A[i] is odd for odd i. Then i + A[i] is always even.
    Aha, ok there are no such conditions. i is an index of the array. it can span from 0..n . A[i] is a value associated with that index which is some value b. so every A[i] has its corresponding b so you can say that there exist another array b that holds those elements but form my naive perspective this is not important(however this may be important while proving the condition stated in my initial post). The only condition is that a for A[i] = b, A[i+1] >= b-1 and that this A[n-b] = b, A[n-b+1] = b-1 ... A[n] = 0 is how the whole thing finishes. Also it is true that b<n.

    An example:

    A: 0 1 2 3 4 5 6 7 8 9
    b: 4 3 2 4 3 4 3 2 1 0


    I wish to prove that :

    |A[i..i+x]| +A[i+x+1] <= A[i] + A[j] for x<=j and i+A[i] = j

    i=0 ,x=1,j= 0 + 4

    so :

    |A[i..i+x]| = 2
    A[i+x+1]= 2
    A[i] = 4
    A[j] = 3

    therfore:

    2+2 <= 4+3
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jun 2012
    From
    Riverside
    Posts
    9
    Thanks
    2

    Re: How to prove it

    Ok, so I'm still kind of confused based on the parameters but see if my logic is correct and I may have a proof.

    |A[i..i+x]|=x-i+1<=j-i+1=A[i]+1, since A[i]=j-i

    A[i+x+1]<=A[i+j+1]-1<=A[j]-1

    so |A[i..i+x]|+A[i+x+1]<=A[i]+1+A[j]-1=A[i]+A[j]

    Let me know which steps I are not solid if any...
    Thanks from baxy77bax
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: How to prove it

    Quote Originally Posted by Jzon758 View Post
    |A[i..i+x]|=x-i+1
    No, |A[i..i+x]| = x + 1. I made a mistake in post #3 in this regard.

    I am still not sure if there is an additional array b or not. If yes, then in general the condition

    If A[i] = b then A[i+1] >= b-1 (*)

    does not say anything about A because it may be that A[i] ≠ b[i] for all i. For each A, one can select an array b such that A[i] ≠ b[i] for all i. Then (*) is true, so the conclusion

    |A[i..i+x]| +A[i+x+1] <= A[i] + A[j] (**)

    has to be true for this arbitrary A. Are you prepared to claim that (**) holds for all arrays A?

    On the other hand, if b is not a separate array, then it is misleading to say (post #1): "every number A[i] in this interval is associated with a number b." Then b is that number A[i]; it is not associated to it! So, by (*), do you mean that A[i+1} >= A[i] - 1 for all i?

    Also, I am still not clear why i + A[i] = j has a solution i. Suppose you are asked: "Find the value of f(x) = x^2 + 3x - 4 for the real number x such that x^2 = -1." This problem is ill-formed. All terms that are part of the claim must be well-defined, and it is not clear to me why i is well-defined, i.e., why it exists for all arrays A. Or do you mean to say, "for any x, j and any i such that i + A[i] = j, prove (**)"? In this case, if such i does not exist, then there is nothing to prove.

    Quote Originally Posted by baxy77bax View Post
    An example:

    A: 0 1 2 3 4 5 6 7 8 9
    b: 4 3 2 4 3 4 3 2 1 0


    I wish to prove that :

    |A[i..i+x]| +A[i+x+1] <= A[i] + A[j] for x<=j and i+A[i] = j

    i=0 ,x=1,j= 0 + 4

    so :

    |A[i..i+x]| = 2
    A[i+x+1]= 2
    A[i] = 4
    A[j] = 3
    If A[i] = 4 for this given A, then i = 4 and i + A[i] = 4 + 4 ≠ 4 = j. There is the only i such that i + A[i] = j, and that is i = 2. On the other hand, there is no such i for j = 5. See what I mean about being well-defined? Also, A[j] = 4, not 3.

    Consider A that is a long sequence of 1's and the last element 0. Take i = 0 and x to be close to the length of A. Then |A[i..i+x]| = x + 1 is large, so x + 1 + A[i+x+1] won't be <= A[i] + A[j] because A[i] + A[j] <= 2.
    Thanks from baxy77bax
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Oct 2008
    Posts
    54

    Re: How to prove it

    Wow, ok now you see why i have said that i am not in the branch

    Quote Originally Posted by emakarov View Post
    I am still not sure if there is an additional array b or not. ...

    On the other hand, if b is not a separate array, then it is misleading to say (post #1): "every number A[i] in this interval is associated with a number b."
    Yes this is my bad and it is misleading. So what i have is one array with indexes 0..9 and their associated values b:4,3,2,..0. The reason why i have said two arrays is because i am usually separating indexes from their values, ergo two arrays (due to some technical reasons where i am treating indexes as a separate array). But you are right, i can see now how this can be misleading.

    Quote Originally Posted by emakarov View Post
    So, by (*), do you mean that A[i+1} >= A[i] - 1 for all i?
    when you put it like this, then yes.


    As far as the rest of the post goes it looks to me that you are saying i need to show that for every array A there exists such i so that i+A[i] = j. I mean there will always be such i that the former holds because the number in the array A are generated so that A[i+1] >= A[i]-1 (or as i wrote previously b-1 where b=A[i]) and that i+A[i] <=n, and since j<=n. I have a feeling that i am not explaining things very well. What i have is exactly the example i posted above where A is an index array and b's are their associated values, so A[4]=3.

    But thank you for all the help , to both of you !! this so far really helped

    baxy
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: How to prove it

    I should probably have realized that there is a single array. I am used to the definition that says that array of elements of X is a function from an index set (usually an interval [0, ..., n] or some other contiguous set of natural numbers) into X. Thus, each index (element of an index set) is associated with an element of X.

    Quote Originally Posted by baxy77bax View Post
    As far as the rest of the post goes it looks to me that you are saying i need to show that for every array A there exists such i so that i+A[i] = j. I mean there will always be such i that the former holds because the number in the array A are generated so that A[i+1] >= A[i]-1 (or as i wrote previously b-1 where b=A[i]) and that i+A[i] <=n, and since j<=n.
    This does not guarantee the existence of i for all j. In your example, such i exists only for j = 4, 7 and 9. For instance, there is no i such that i + A[i] = 5.

    Also, has it been mentioned before that i+A[i] <= n?

    Quote Originally Posted by baxy77bax View Post
    An example:

    A: 0 1 2 3 4 5 6 7 8 9
    b: 4 3 2 4 3 4 3 2 1 0


    I wish to prove that :

    |A[i..i+x]| +A[i+x+1] <= A[i] + A[j] for x<=j and i+A[i] = j
    I believe the following is a counterexample based on the data above. If i = 0 and j = x = 4, then x <= j and i + A[i] = j, as required; however, (x + 1) + A[i+x+1] = 5 + 4 = 9 while A[i] + A[j] = 4 + 3 = 7.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove cot(a)+cot(b)+cot(c)=cot(a).cot(b).cot(c)
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: June 18th 2011, 11:45 PM
  2. how to prove this..?
    Posted in the Calculus Forum
    Replies: 4
    Last Post: June 6th 2010, 01:19 AM
  3. Prove that deg(f(x)g(x))=deg(f(x))+deg(g(x))
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 18th 2009, 04:00 PM
  4. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  5. prove that ...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 12th 2008, 08:55 PM

Search Tags


/mathhelpforum @mathhelpforum