Thread: Please help: proof involvim array elements :CS

Hi,


well i need some help with the following problem. I have posted fractions of this problem before and got very helpful comments. Now when the Proof is nearly done i need for someone to check it and tell me how bad the proof is. So let me recapitulate. This is a toy problem connected to CS class. What i have is :



Defn_1:

$\displaystyle x_{1} = a$
$\displaystyle x_{p+1} = x_{p} + A[x_{p}]$

where
1. 0<A[a]<=n
2. A[a]-1 <= A[a+1] for 0<=a<=A[l]
3. A[a]-1 = A[a+1] for n-A[l]< a <= n

A[a] is an array value on position a. A[l] is the last array value such that A[l-1] < A[l] and A[l] > A[l+1] , su A[l] is the last local maximum


Defn_2:

$\displaystyle y_{1} \leq A[a] $
$\displaystyle y_{p+1} \leq A[a+\sum^{p}_{n=1} y_{n}] $

Problem:

If y>=1 then $\displaystyle k\leq \sum^{k}_{p=1} y_{p} \leq \sum^{k}_{p=1}A[x_{p}]$.

Proof:

Suppose $\displaystyle y \geq 1$. Suppose $\displaystyle \sum^{k}_{p=1} y_{p} < k$. By plugging in $\displaystyle y_{p+1} = y_{p} = 1 $ we get $\displaystyle \sum^{k}_{p=1} y_{p} = k < k$ which is a contradiction. Thus for $\displaystyle y \geq 1$, $\displaystyle \sum^{k}_{p=1} y_{p} \geq k$. Furthermore, by definition 2 we have $\displaystyle y_{1} \leq A[a] $ and $\displaystyle y_{p+1} \leq A[a+\sum^{p}_{n=1} y_{n}] $
thus:

$\displaystyle \sum^{k}_{p=1} y_{p} = y_{1}+y_{2}+ .. y_{k} $
$\displaystyle \sum^{k}_{p=1} y_{p} \leq A[a] + A[a+\sum^{p}_{f=1} y_{f}] + ... A[a+\sum^{k-1}_{f=1} y_{f}] $ by defn 2
$\displaystyle \sum^{k}_{p=1} y_{p} \leq A[x_{1}] + A[x_{2}] + ... A[x_{k}]$ by defn 1
$\displaystyle \sum^{k}_{p=1} y_{p} \leq \sum^{k}_{p=1} A[x_{p}] $

Therefore if y>=1 then $\displaystyle k\leq \sum^{k}_{p=1} y_{p} \leq \sum^{k}_{p=1}A[x_{p}]$.



_________________


So this is how far i came. However i feal that i am missing something since my domain (array length) is limited. Or should i say, i feal that the above would hold if array was infinite in size. Also to depict the problem i am going to give an example:

A is my array

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

the claim that i should prove is, if i make k jumps where k im my example let say is 1, the the distance if i start in 0 -> A[0]=7 equals 10 since |A[0]| + |A[7]| = 10. But this will not hold if my k =4 because then i am out of range. and this is what is bugging me. all examples that i have seen up until now are working with sets that are infinite in size and i have not seen an example that is limited by a size....

so please help by giving an advice on what should i read or what should i do to make my proof and problem definition correct. And please check what nonsense have i written in the section above. Remember that i am still learning how to prove claims.

Thank you

baxy

Hey baxy77bax.

So basically you want to find the conditions when your array indices are in range so you can calculate your function corresponding to x_p for some value of p?