Proof by induction - Really confused

[Tvtakaveli]

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.

 

[MarkFL]

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?

 

[Tvtakaveli]

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.

 

[MarkFL]

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?

 

[Tvtakaveli]

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.