Proof by induction (Implication)

[kasper_2211]

Homework Statement

The problem statement is as follows:
Let T be a ordered list(sequence) with N entrys. Prove by induction that, <br /> j-i&lt; 2^{n} \Rightarrow A(i,j) \leq n for all integers i, j, n where 1 \leq i \leq j \leq Nand n \geq 0

A(i, j) is the number of steps taken by a certain recursive algorithm (much like Binary search). So for example a call A(1, 12) will take 4 steps to complete, and thus A(1, 12) = 4.

Homework Equations

The Attempt at a Solution

I don't have much of an idea where to start. What i think i should do is assume that the left hand side of the implication is true, and then show the right hand side must also be true. Also, I am thinking that i need another way to define A(i, j). Maybe like an equation or recurrence relation. Right now i only have test's showing me that the algorithm runs in log n time. Really what I am looking for is not a solution to the problem but just a pointer in the right direction, as to how to prove implications like this one. Any help is much appreciated.

P.S. I have done inductive proofs before, but this one seems strange to me.

 

[willem2]

The left hand side of the implication is &lt; 2^n, so that makes no sense, and I have no idea what A(i,j) is

 

[kasper_2211]

I pushed the wrong button and published some gibberish before i was finished writing. Sorry about that.

 

[willem2]

I pushed the wrong button and published some gibberish before i was finished writing. Sorry about that.

I still don't know how to find the values of A(i,j). Also the list T doesn't appear in the implication.

 

[kasper_2211]

Yeah, i wish i could explain things better. The way the algorithm is called is by A(1, N), where N is the length of the sequence T (the algorithm is not actually given a list T as input, since it's not "a real algorithm"). So N = 12 in the example A(1, 12). The algorithm is given parameters 1 and N and will return true if 0 is in the sequence. This is achieved much like binary search by cutting the sequence in half, until only one "cell" is left. Then it checks to see if 0 is in that cell and returns true or false. In that sense it will always have the same running time, depending on the size of N, since it is not checking to see if 0 is found "while running". But it is exacly my problem...that i can't figure out a way to express A(i, j) in a way that makes sense. If any help here is some kind of pseudo-code for the algorithm.

A(i, j): 
if j = i then
  return T[i]=0             
else
  k = i + floor((j - i) / 2)
  if T[k] ≥ 0 then 
    return A(i, k)
  else
    return A(k+1, j)

And here a very quick implementation in SML that actually takes a list:

fun A (i, j, t) = 
    let 
	val n = 0
	val T = t

	fun test (i, j, n) = 
	    if i = j 
	    then if List.nth(T, floor(i)) = 0
		 then (n, true, floor(i + 1.0)) 
		 else (n, false,floor(i + 1.0))  
	    else 
		let val k = (floor(i) + (floor((j - i) / 2.0)))
		in
		    if List.nth(T, k) >= 0 
		    then test (i, real(k), n + 1)
		    else test (real(k + 1), j, n + 1)	 
		end
    in
	test (i, j, n)
    end

val t = [~211, ~101, ~80, ~45, 0, 3, 42, 80, 204, 320, 325, 531]

val t_0 = A (1.0, 12.0, t)
RETURNS: (4, true, 5) : int * bool * int
Where, 
4 is the steps taken to terminate, 
true means 0 is in the list 
5 means 0 is in cell 5 of the list (4 if zero-based)

 

[willem2]

You can do induction on n. the base case n=0
you have to prove if j-i <1 => A(i,j) <= 0.

induction you can assume j-i<2^n => A(i,j) <= n
and have to prove j-i<2^(n+1) => A(i,j) <= n+1

 

[kasper_2211]

Thanks! That got me started! I can find and prove the base case. I did not write it in the problem statement, but by definition a call A(i, i) = 0. So if j - i < 1, then j = i and then A(i, i) = 0. So the base case is ok. So, i guess for the next part i need something similar. I am still confused about what to do though. I mean, i can't really prove that the left side of the implication will be true for 2^(n+1), since that's not going to hold for all i, j, n. I am assuming that j-i<2^n => A(i, j) <= 0, but where should that assumption be used? If i could "split it up" and assume that j-i < 2^n, then it would be trivially true that j-i < 2^(n+1), which seems absurd.
My thought right now is to rewrite the left side, j-i < 2^(n+1) somehow, and figure out what that tells me about i, j and n...but I am still stuck. Basically what confuses me is that i need to prove an implication, and not as i am more used to, statements about say divisibility or sequences. Any hints? Thanks...

P.S. Please don't post complete solutions.

 

[willem2]

My thought right now is to rewrite the left side, j-i < 2^(n+1) somehow, and figure out what that tells me about i, j and n...but I am still stuck. Basically what confuses me is that i need to prove an implication, and not as i am more used to, statements about say divisibility or sequences. Any hints? Thanks...

P.S. Please don't post complete solutions.

to prove j-i<2^(n+1) => A(i,j) <= n+1

you assume j-i<2^(n+1) and use this with the
induction hypothesis if j-i <1 => A(i,j) <= n to prove A(i,j) <= n+1

what happens if you call A with j-i<2^(n+1) ?

 

[kasper_2211]

Ok, so now i "completely" understand the logic behind the proof.
Show basecase,
j - i < 1 => A(i,j) <= 0
Now assume that,
j - i < 2^n => A(i, j) <= n for some arbitrary n. This is the induction hypothesis.
Now assume that,
j - i < 2^(n+1) and show that this implies A(i, j) <= n +1

BUT, i can't see what happens when i call A with for example j - i < 2^(n+1). Even though i assume this inequality to be true it doesn't tell me anything about j and i. Furthermore i only now what happens when calling A(i, i), since that by definition is 0.
Can i say that since i assume j - i < 2^(n+1) that implies j - i < 2^n because of the inductive hypothesis, and that implies A(i, j) <= n which means A(i, j) <= n +1 = A(i, j) - 1 <= n?? This seems wrong to me...

 

[kasper_2211]

Or maybe i need to show that if I call A with j - i < 2^(n+1), then for the first recursive call j - i will be less than 2^n, and then by the induction hypothesis that will imply A(i, j) <= n which is less than n + 1??
The first step in the algorithm is to cut the list in half...so when i call A with j - i < 2^(n+1) i know the difference j - i is less than 2 * 2^n, and if it's cut in half it is less 2^n?

 

[willem2]

Or maybe i need to show that if I call A with j - i < 2^(n+1), then for the first recursive call j - i will be less than 2^n, and then by the induction hypothesis that will imply A(i, j) <= n which is less than n + 1??
The first step in the algorithm is to cut the list in half...so when i call A with j - i < 2^(n+1) i know the difference j - i is less than 2 * 2^n, and if it's cut in half it is less 2^n?

I think that's it. You should be getting A(i, j) <= n+1 instead of A(i, j) <= n because 1 gets added to n

 

[kasper_2211]

Thanks a lot! I think i got it now. I will post the final proof here when the homework is turned in (don't want to get in trouble for posting the final solution before that). But thanks a lot for the help.