Proof by induction - Really confused

Tvtakaveli

New member
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

Staff member
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:

$$\displaystyle O_1=1$$

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

$$\displaystyle O_n=n^2$$

And we are told:

$$\displaystyle 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

New member
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 im 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

MarkFL

Staff member
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 im 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

$$\displaystyle O_n=n^2$$

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

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

We get:

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

And upon factoring the RHS, we have:

$$\displaystyle 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

New member
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.