Mathematical induction problem

In summary, mathematical induction is a proof technique used to prove that a statement is true for all natural numbers. It involves two steps: the base case and the induction step. It is commonly used to solve problems involving series and sequences, divisibility, and inequalities. There are two types of mathematical induction: strong and weak, which differ in the inductive hypothesis. Some common mistakes when using mathematical induction include forgetting to prove the base case, assuming the statement is true without proper proof, and using the wrong inductive hypothesis. However, it cannot be used to prove statements that are only true for a specific set of numbers or for infinite sets.
  • #1
DDarthVader
51
0

Homework Statement


Hello! This is I want to prove using Mathematical Induction: [itex]1+3+5+...+(2n-1)=n^2[/itex]. The problem is: I don`t understand very much about Mathematical Induction :(

Homework Equations


The Attempt at a Solution


Suppose n=1. Then 1=1. Now suppose [itex]1+3+5+...+(2n)=(n+1)^2[/itex]. Then [itex]1+3+5+...+2n=(1+3+5+...+(2n-1))+2n=n^2+2n=n(n+2)[/itex].
Is this correct? If yes, how does this prove my hypothesis?
 
Physics news on Phys.org
  • #2
You're only working with odd numbers, so the next term wouldn't be [itex]2n[/itex]..
 
  • #3
This is what I should do to solve the problem [itex]1+3+5+...+(2n-1+1)=1+3+5+...+2n[/itex]. Right? Because you always do [itex]n+1[/itex] in the Induction step.
 
  • #4
DDarthVader said:

Homework Statement


Hello! This is I want to prove using Mathematical Induction: [itex]1+3+5+...+(2n-1)=n^2[/itex]. The problem is: I don`t understand very much about Mathematical Induction :(


Homework Equations





The Attempt at a Solution


Suppose n=1. Then 1=1. Now suppose [itex]1+3+5+...+(2n)=(n+1)^2[/itex]. Then [itex]1+3+5+...+2n=(1+3+5+...+(2n-1))+2n=n^2+2n=n(n+2)[/itex].
Is this correct? If yes, how does this prove my hypothesis?

Mathematical induction attempts to show that if the equation holds for n, then it also holds for n+1. It's easier to keep straight if you use a substitution such as n=k+1
 
  • #5
@ DDarthVader: Yes, but you're not substituting [itex]n + 1[/itex] in for [itex]2n - 1[/itex] or anything, you're subbing it in for [itex]n[/itex]...
 
  • #6
Doing the substitution [itex]n=k+1[/itex] I've got this result:
[itex] 1+3+5+...+2k+1=(1+3+5+...+(2n-1))+2k+1[/itex]
Then
[itex]n^2 +2k+1 = (k+1)^2+2k+1 = k^2+2k+2+2k+1 = k^2+4k+3[/itex]
But since [itex]n=k+1[/itex] we got
[itex](n-1)^2+4n-4+3 =n^2-2n+4n+1 =n^2+2n+1 = (n+1)^2[/itex]
Is this correct?
 
Last edited:
  • #7
Your conjecture: [itex]1+3+5+...+(2n-1)=n^2[/itex]

You've already done the base step, n = 1.

For the induction step:

Let k ≥ 1. Assume that your conjecture is true for n = k. From that, show (prove) that your conjecture is true for n = k+1 .

So you need to show that [itex]1+3+5+\dots+(2k-1)+(2(k+1)-1)=(k+1)^2[/itex] is true,

starting with [itex]1+3+5+\dots+(2k-1)=k^2\ .[/itex]
 
Last edited:
  • #8
DDarthVader said:

Homework Statement


Hello! This is I want to prove using Mathematical Induction: [itex]1+3+5+...+(2n-1)=n^2[/itex]. The problem is: I don`t understand very much about Mathematical Induction :(

Homework Equations



The Attempt at a Solution


Suppose n=1. Then 1=1. Now suppose [itex]1+3+5+...+(2n)=(n+1)^2[/itex]. Then [itex]1+3+5+...+2n=(1+3+5+...+(2n-1))+2n=n^2+2n=n(n+2)[/itex].
Is this correct? If yes, how does this prove my hypothesis?

As you see here, (n+1)th value is not equal to 2n
It is equal to (2(n+1)-1)
 
  • #9
DDarthVader said:
Doing the substitution [itex]n=k+1[/itex] I've got this result:
[itex] 1+3+5+...+2k+1=(1+3+5+...+(2n-1))+2k+1[/itex]
Then
[itex]n^2 +2k+1 = (k+1)^2+2k+1 = k^2+2k+2+2k+1 = k^2+4k+3[/itex]
But since [itex]n=k+1[/itex] we got
[itex](n-1)^2+4n-4+3 =n^2-2n+4n+1 =n^2+2n+1 = (n+1)^2[/itex]
Is this correct?

Substituting n=k+1 into 2n-1 gives 2(k+1)-1.
 
  • #10
SammyS said:
Your conjecture: [itex]1+3+5+...+(2n-1)=n^2[/itex]

You've already done the base step, n = 1.

For the induction step:

Let k ≥ 1. Assume that your conjecture is true for n = k. From that, show (prove) that your conjecture is true for n = k+1 .

So you need to show that [itex]1+3+5+\dots+(2k-1)+(2(k+1)-1)=(k+1)^2[/itex] is true,

starting with [itex]1+3+5+\dots+(2k-1)=k^2\ .[/itex]

Doing what you told me I've got this result:
[itex]1+3+5+...+(2n-1)=n^2[/itex].
We assume n=k. Then we try to prove if the conjecture is true for n=k+1 and we obtain: [itex]1+3+5+...+(2n-1)+(2n-1)=n^2[/itex]
But n=k+1
[itex]k^2+(2(k+1)-1)=(k+1)^2[/itex]
[itex]k^2+(2(k+1)-1)=k^2+2k+1[/itex]
[itex]2(k+1)-1=2k+1[/itex]
[itex]2(k+1)=2k+2[/itex]
[itex]2(k+1)=2(k+1)[/itex]
So I proved that the conjecture is also true for n=k+1. Right?
 
  • #11
DDarthVader said:
Doing what you told me I've got this result:
[itex]1+3+5+...+(2n-1)=n^2[/itex].
We assume n=k. Then we try to prove if the conjecture is true for n=k+1 and we obtain: [itex]1+3+5+...+(2n-1)+(2n-1)=n^2[/itex]
But n=k+1
[itex]k^2+(2(k+1)-1)=(k+1)^2[/itex]
[itex]k^2+(2(k+1)-1)=k^2+2k+1[/itex]
[itex]2(k+1)-1=2k+1[/itex]
[itex]2(k+1)=2k+2[/itex]
[itex]2(k+1)=2(k+1)[/itex]
So I proved that the conjecture is also true for n=k+1. Right?

Isn't it bad practice to manipulate both sides of an equation in a problem such as this?
 
  • #12
DDarthVader said:
Doing what you told me I've got this result:
[itex]1+3+5+...+(2n-1)=n^2[/itex].
We assume n=k. Then we try to prove if the conjecture is true for n=k+1 and we obtain: [itex]1+3+5+...+(2n-1)+(2n-1)=n^2[/itex]
But n=k+1
[itex]k^2+(2(k+1)-1)=(k+1)^2[/itex]
[itex]k^2+(2(k+1)-1)=k^2+2k+1[/itex]
[itex]2(k+1)-1=2k+1[/itex]
[itex]2(k+1)=2k+2[/itex]
[itex]2(k+1)=2(k+1)[/itex]
So I proved that the conjecture is also true for n=k+1. Right?
Yes, somewhat indirectly.

Rather you should do something like the following.

Assume [itex]1+3+5+\dots+(2k-1)=k^2\ .[/itex]

Now consider:

[itex]1+3+5+\dots+(2k-1)+(2(k+1)-1)[/itex]
[itex]=k^2+(2(k+1)-1)[/itex]   ... because of or assumption.

[itex]=k^2+2k+1[/itex]

[itex]=(k+1)^2[/itex]  Which is what we needed to show for the inductive step.​

It's not that what you did is particularly wrong, it's just that it's not real clear that you're not somehow assuming the very thing you should be proving.
 
Last edited:
  • #13
It's generally frowned upon to work both sides at once, yeah. Usually, one would take [itex]k^2 + 2(k+1)-1[/itex] and manipulate it until it's clear the result is [itex](k+1)^2[/itex]. Working only in one direction ensures that no illegal operations or cancellations are done, even though it may be necessary to set both sides equal just to figure out how to do it.
 
  • #14
Well, I think I got it now! I have a list of mathematical induction to do. I'll try to solve the exercises using what you guys told me. I'll probably be back soon. Thanks guys!
 
  • #15
Prove by mathematical induction that n^3-n is divisible by 2 for all positive integral values of n.
Please help me in solving this question!
 
  • #16
amrah said:
Prove by mathematical induction that n^3-n is divisible by 2 for all positive integral values of n.
Please help me in solving this question!

Please create a new thread for this.

Also, show how you approached it so we can help you better! :smile:

As a start...try showing it is true for n=1..then assume it to be true for n=k...
 

1. What is mathematical induction?

Mathematical induction is a proof technique used to prove that a statement 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 shown that if the statement is true for one natural number, it is also true for the next natural number.

2. How is mathematical induction used to solve problems?

Mathematical induction is used to prove that a statement is true for all natural numbers. This can be useful in solving various types of problems, such as series and sequences, divisibility, and inequalities.

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

The difference between strong and weak induction lies in the inductive hypothesis. In strong induction, the hypothesis assumes that the statement is true for all previous natural numbers, while in weak induction, the hypothesis only assumes that the statement is true for the previous natural number.

4. What are the common mistakes made when using mathematical induction?

Some common mistakes made when using mathematical induction include forgetting to prove the base case, assuming the statement is true for all natural numbers without proper proof, and using the wrong inductive hypothesis.

5. Can mathematical induction be used to prove all statements?

No, mathematical induction can only be used to prove statements that are true for all natural numbers. It cannot be used to prove statements that are only true for a specific set of numbers or for infinite sets.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
10
Views
737
  • Precalculus Mathematics Homework Help
Replies
13
Views
1K
  • Precalculus Mathematics Homework Help
Replies
13
Views
2K
  • Precalculus Mathematics Homework Help
Replies
31
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
Back
Top