Proof by induction (Implication)

In summary, the problem statement is to prove by induction that for an ordered list T with N entries, if j-i < 2^n, then A(i,j) <= n for all integers i, j, n where 1 <= i <= j <= N and n >= 0. A(i,j) represents the number of steps taken by a recursive algorithm similar to binary search. The algorithm is called by A(1,N) where N is the length of the sequence. The base case can be proven by showing that if j-i < 1, then A(i,i) = 0. For the inductive step, it can be assumed that j-i < 2^n => A(i,j) <= n and the goal
  • #1
kasper_2211
13
0

Homework Statement


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

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.
 
Last edited:
Physics news on Phys.org
  • #2
The left hand side of the implication is [itex] < 2^n [/itex], so that makes no sense, and I have no idea what A(i,j) is
 
  • #3
I pushed the wrong button and published some gibberish before i was finished writing. Sorry about that.
 
  • #4
kasper_2211 said:
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.
 
  • #5
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.

Code:
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)
 
Last edited:
  • #6
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
 
  • #7
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.
 
Last edited:
  • #8
kasper_2211 said:
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) ?
 
  • #9
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...
 
Last edited:
  • #10
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?
 
Last edited:
  • #11
kasper_2211 said:
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
 
  • #12
Thanks alot! 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.
 

1. What is proof by induction?

Proof by induction is a mathematical technique used to prove that a statement holds true for all natural numbers. It involves proving the statement for the first natural number, and then showing that if the statement holds true for any given natural number, it also holds true for the next natural number.

2. How does proof by induction work?

Proof by induction works by breaking down a statement into smaller, more manageable parts. The base case, which is usually the first natural number, is proven to be true. Then, the inductive step is used to show that if the statement holds true for one natural number, it also holds true for the next natural number. This process is repeated until the statement is proven to hold true for all natural numbers.

3. When is proof by induction used?

Proof by induction is often used in mathematics to prove the validity of a statement for all natural numbers. It is commonly used in areas such as number theory, algebra, and combinatorics.

4. What are the requirements for using proof by induction?

The statement being proven must be applicable to natural numbers, and it must be divisible into smaller, simpler parts. Additionally, the base case must be proven to be true, and the inductive step must be logically sound and applicable to all natural numbers.

5. Are there any limitations to proof by induction?

Proof by induction can only be used to prove statements that are applicable to natural numbers. It is also not a valid proof technique for proving statements about real numbers or continuous functions. Additionally, if the statement being proved is not true for the base case, then the entire proof by induction is invalid.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
Replies
5
Views
270
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
12
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Topology and Analysis
Replies
2
Views
2K
Back
Top