MHB Proof by induction - Really confused

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.
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.
Back
Top