Thread: Proving the lower bound of the order

Hi,

I guess this i rather simple task but somehow i cannot get my head arround it. So what i have is a set S of random numbers that are generated in the following way:


get a number (random 1-10)

for 1 to inf
get a number (random 1-10) bigger or equal to the number on a prevoius position minus 1


So the set looks like this:

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


what i want to show is that for some integer z in I, if z is smaller then the value on position i then the value on position i minus z <= then the value on position (i plus z).

so
i= 4
value of i = 8
z= 5
i+z= 9
value of 9 = 6
if z< 8 then 8-4 <= 6

Can someone give me a kick in the right direction?

thank you !

Hi, i understand the first part (how you construct S)

But please clarify what you need to prove

so what i want to show is that for some integer z which is smaller then a value on position i, a value on position i+z will be smaller or equal then the value on i. i is some number x - z

i don't know how to elaborate on this in any other way. so let say i am looking at the first position (f(i=1) = 5) then if i pick any z value that is smaller then 5 let say z = 2 then i can claim that a value on position (i+2 = 1+2 = 3) 3 will be bigger or equal to f(i=3) = f(i=1) - 2 = 3. and i can see that on i=3 my f(i=3)=9 which is bigger then 3

now let say I pick i = 4 then f(i=4) = 8. now I want to show that if I pick z=3 that f(i=4+3) >= 8-3 = 5 and I can see that on a position i=7 , f(i=7)=5 which is >= 8-3 = 5.

so all i want to show is if i use the algorithm that i have described which generates one number based only on the number before , i can say something about the any number j given that I know the distance from i to j and the value of i (f(i)). And the thing i would like to say is that for any z<f(i), f(i+z) >= f(i) + z.

hope this makes it a bit more helpfull, and thnx for showing interest.

baxy

A correction:

And the thing i would like to say is that for any z<f(i), f(i+z) >= f(i) - z. ?????

(you put f(i)+z at the end but i think is f(i)-z ???)

Hi again, i think i got it

From the fact that you select in the position i+1 a number greater or equal than f(i) we have that

f(i+1)>= f(i)-1
f(i+2)>=f(i+1)-1 >= f(i)-2
f(i+3)>=f(i+2)-1>=f(i+1)-2>=f(i)-3

......

f(i+z)>=f(i)-z

Steve