Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By chiro

Thread: Please help: proof involvim array elements :CS

  1. #1
    Junior Member
    Oct 2008

    Please help: proof involvim array elements :CS


    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 :


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

    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


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


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


    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}] $

    $\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

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Sep 2012

    Re: Please help: proof involvim array elements :CS

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

Similar Math Help Forum Discussions

  1. Replies: 8
    Last Post: Nov 27th 2011, 10:18 PM
  2. Herstein: Simple proof with elements.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Oct 9th 2011, 12:29 PM
  3. Replies: 5
    Last Post: Jun 21st 2010, 02:31 PM
  4. array help
    Posted in the LaTeX Help Forum
    Replies: 1
    Last Post: Oct 12th 2008, 04:42 PM
  5. Proof of intersect between 2 elements of group G
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 21st 2008, 06:36 AM

Search Tags

/mathhelpforum @mathhelpforum