MHB Proof by induction - Really confused

AI Thread Summary
The discussion revolves around proving two statements using mathematical induction. The first statement asserts that a sorting algorithm requires at most n^2 operations to sort an array with n > 0 items, starting with the base case of one item. The second statement claims that for n ≥ 1, the expression 7n − 1 is a multiple of 6. Participants clarify the induction process, emphasizing the importance of establishing a clear induction hypothesis and demonstrating how to derive the next case from the previous one. Ultimately, the proof for the sorting algorithm is confirmed by showing that O_{n+1} equals (n+1)^2, validating the initial hypothesis.
Tvtakaveli
Messages
5
Reaction score
0
Hi again. I have one other problem I'm puzzled about.

(a) A sorting algorithm takes one operation to sort an array with one item in it.
Increasing the number of items in the array from n to n + 1 requires at most an
additional 2n + 1 operations. Prove by induction that the number of operations
required to sort an array with n > 0 items requires at most n^2 operations.
(b) Show by induction that if n ≥ 1, then 7n − 1 is a multiple of 6.

So I'm confused to what the question even is and how to put it into a statement. Thank you.
 
Physics news on Phys.org
Tvtakaveli said:
Hi again. I have one other problem I'm puzzled about.

(a) A sorting algorithm takes one operation to sort an array with one item in it.
Increasing the number of items in the array from n to n + 1 requires at most an
additional 2n + 1 operations. Prove by induction that the number of operations
required to sort an array with n > 0 items requires at most n^2 operations.
(b) Show by induction that if n ≥ 1, then 7n − 1 is a multiple of 6.

So I'm confused to what the question even is and how to put it into a statement. Thank you.

(a) I would let \(O_n\) be the number of operations it takes to sort an array containing \(n\) elements. Now, we are told:

$$O_1=1$$

And so this satisfies our base case, \(P_1\). We are given the induction hypothesis \(P_n\):

$$O_n=n^2$$

And we are told:

$$O_{n+1}-O_n=2n+1$$

This can serve as our induction step, because we can add this to our induction hypothesis. What do we get?
 
Ohhh okay that makes a lot more sense. See the induction examples I find online aren't very helpful because they were just substituting n values.

I'm guessing now we would try to get both sides to be equivalent. So either by substituting a value for n that's greater than 0.
Or by just rearranging the formula so that both have the same.

Again I am missing something I just can't work it out.
So
On+1−On=2n+1
n^2+1 - n^2=2n+1
But that wouldn't make sense because
1^2+1 - 1^2 =0. 2*1+1=3

Thanks in advance.
 
Tvtakaveli said:
Ohhh okay that makes a lot more sense. See the induction examples I find online aren't very helpful because they were just substituting n values.

I'm guessing now we would try to get both sides to be equivalent. So either by substituting a value for n that's greater than 0.
Or by just rearranging the formula so that both have the same.

Again I am missing something I just can't work it out.
So
On+1−On=2n+1
n^2+1 - n^2=2n+1
But that wouldn't make sense because
1^2+1 - 1^2 =0. 2*1+1=3

Thanks in advance.

If we start with our induction hypothesis:

$$O_n=n^2$$

And add to this the induction step implied by the problem statement:

$$O_{n+1}-O_n=2n+1$$

We get:

$$O_{n+1}=n^2+2n+1$$

And upon factoring the RHS, we have:

$$O_{n+1}=(n+1)^2$$

And now we find that we've derived \(P_{n+1}\) from \(P_n\), thereby completing the proof by induction.

Does that make sense?
 
Ahhhh so it proves the hypothesis. I see now factorising was the way to do it. It's a lot more clear now thank you for the assistance. I really appreciate it.
 
Back
Top