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

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.

Quote:

---

Originally Posted by baxy77bax

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

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

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?

Quote:

---

Originally Posted by Jzon758

This is for computer science?

---

yes

Quote:

---

Originally Posted by Jzon758

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

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

Quote:

---

Originally Posted by emakarov

So, there is another array b[0..n], right?

---

Yes

Quote:

---

Originally Posted by emakarov

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

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

So, |A[i..i+x]| = x-i+1?

---

yes

Quote:

---

Originally Posted by emakarov

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

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

Quote:

---

Originally Posted by baxy77bax

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.

Quote:

---

Originally Posted by emakarov

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

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

Quote:

---

Originally Posted by Jzon758

|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

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.

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

Quote:

---

Originally Posted by emakarov

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

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

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

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

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.