Thread: Induction and more.

N is Z loadet in a table T in the spots 1,2,...,N, arranged so that the number in spot i always is smaller og equal to the number on the spot i+1.
Example given.
-1212 | -1002 | -800 | -545 | -123 | -54 | -2 | 0 | 4 | 321 | 324 | 501

(N = 12), We wish to determine wether 0 is part of this table og look at the following algorithm.

Psedu code picture by krakatau7 - Photobucket

Question (B)

Consider a random arranged table T with N entries (inputs?). Prove by induction this claim:



for every Z i,j,n with

Bumping this thread, as I have modified a bit in the text.

so my first thoughts are

Basic step P(o) = j - i < 1 => A(j,i) O

Is this our basic step?

furthermore

we assume P(n) j-i < 2^n => A(j,i) n

is TRUE

and now we want to prove P(n+1) is true

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

if we want to prove this, we need to show that

A(j,i) n+1

to prove this our teacher said we could use j' - i' < 2^n+1
and remake 2^n+1 into 2^n *2

I understand the rule of operation, but I dont see how this can help us to reach further in the induction.