# Proof by induction - Really confused

• MHB
• Tvtakaveli
In summary, 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=1And so this satisfies our base case, $$P_1$$. We are given the induction hypothesis $$P_n$$:O_n=n^2And we are told:O_{n+1}-O_n=2n+1This 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
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.

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:

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

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

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

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

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.

## 1. How does proof by induction work?

Proof by induction is a mathematical technique used to prove that a statement or formula is true for all natural numbers. It involves two steps: the base case, where the statement is shown to be true for the first natural number, and the induction step, where it is proven that if the statement is true for a particular natural number, it is also true for the next natural number. This process is repeated until it is shown to be true for all natural numbers.

## 2. When is proof by induction used?

Proof by induction is commonly used in mathematics and computer science to prove the validity of statements or formulas that hold true for all natural numbers. It is often used to prove theorems, identities, and equations involving sequences, series, and recursive functions.

## 3. What is the difference between weak and strong induction?

Weak induction, also known as mathematical induction, involves proving a statement for a particular natural number and then showing that if it is true for that number, it is also true for the next number. Strong induction, on the other hand, involves proving that if a statement is true for all numbers up to a certain number, it is also true for the next number. In other words, strong induction allows for the use of multiple base cases in the induction step.

## 4. Can proof by induction be used for infinite sets?

No, proof by induction can only be used for finite sets. This is because the base case and induction step require a specific starting point (usually 0 or 1) and a fixed number of steps. For infinite sets, other techniques such as transfinite induction may be used.

## 5. What are some common mistakes to avoid when using proof by induction?

Some common mistakes to avoid when using proof by induction include assuming that the statement is true for all natural numbers without first proving it for the base case, using the wrong induction hypothesis, or making incorrect assumptions in the induction step. It is important to carefully follow the steps of proof by induction and to check for any logical errors in the reasoning.

• Precalculus Mathematics Homework Help
Replies
10
Views
377
• Programming and Computer Science
Replies
10
Views
928
• Calculus and Beyond Homework Help
Replies
7
Views
573
• Calculus and Beyond Homework Help
Replies
7
Views
395
• Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
• General Math
Replies
13
Views
1K
• Calculus and Beyond Homework Help
Replies
15
Views
1K
• Linear and Abstract Algebra
Replies
8
Views
2K
• Calculus and Beyond Homework Help
Replies
5
Views
347
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K