1. ## 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:

$j-i < 2^n \Rightarrow A(i,j) \leq n$

for every Z i,j,n with $1\leq i \leq j \leq N and n \geq n$

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

3. ## am I right?

so my first thoughts are

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

Is this our basic step?

4. furthermore

we assume P(n) j-i < 2^n => A(j,i) $\leq$ 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) $\leq$ n+1

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

A(j,i) $\leq$ 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.