Mathematical induction problem

1. Jun 6, 2012

1. The problem statement, all variables and given/known data
Hello! This is I want to prove using Mathematical Induction: $1+3+5+...+(2n-1)=n^2$. The problem is: I don`t understand very much about Mathematical Induction :(

2. Relevant equations

3. The attempt at a solution
Suppose n=1. Then 1=1. Now suppose $1+3+5+...+(2n)=(n+1)^2$. Then $1+3+5+...+2n=(1+3+5+...+(2n-1))+2n=n^2+2n=n(n+2)$.
Is this correct? If yes, how does this prove my hypothesis?

2. Jun 6, 2012

You're only working with odd numbers, so the next term wouldn't be $2n$..

3. Jun 6, 2012

This is what I should do to solve the problem $1+3+5+...+(2n-1+1)=1+3+5+...+2n$. Right? Because you always do $n+1$ in the Induction step.

4. Jun 6, 2012

sacscale

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. Jun 6, 2012

@ DDarthVader: Yes, but you're not substituting $n + 1$ in for $2n - 1$ or anything, you're subbing it in for $n$...

6. Jun 6, 2012

Doing the substitution $n=k+1$ I've got this result:
$1+3+5+...+2k+1=(1+3+5+...+(2n-1))+2k+1$
Then
$n^2 +2k+1 = (k+1)^2+2k+1 = k^2+2k+2+2k+1 = k^2+4k+3$
But since $n=k+1$ we got
$(n-1)^2+4n-4+3 =n^2-2n+4n+1 =n^2+2n+1 = (n+1)^2$
Is this correct?

Last edited: Jun 6, 2012
7. Jun 6, 2012

SammyS

Staff Emeritus
Your conjecture: $1+3+5+...+(2n-1)=n^2$

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 $1+3+5+\dots+(2k-1)+(2(k+1)-1)=(k+1)^2$ is true,

starting with $1+3+5+\dots+(2k-1)=k^2\ .$

Last edited: Jun 6, 2012
8. Jun 6, 2012

azizlwl

As you see here, (n+1)th value is not equal to 2n
It is equal to (2(n+1)-1)

9. Jun 6, 2012

sacscale

Substituting n=k+1 into 2n-1 gives 2(k+1)-1.

10. Jun 6, 2012

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

11. Jun 6, 2012

Villyer

Isn't it bad practice to manipulate both sides of an equation in a problem such as this?

12. Jun 6, 2012

SammyS

Staff Emeritus
Yes, somewhat indirectly.

Rather you should do something like the following.

Assume $1+3+5+\dots+(2k-1)=k^2\ .$

Now consider:

$1+3+5+\dots+(2k-1)+(2(k+1)-1)$
$=k^2+(2(k+1)-1)$   ... because of or assumption.

$=k^2+2k+1$

$=(k+1)^2$  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: Jun 6, 2012
13. Jun 6, 2012

Muphrid

It's generally frowned upon to work both sides at once, yeah. Usually, one would take $k^2 + 2(k+1)-1$ and manipulate it until it's clear the result is $(k+1)^2$. 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. Jun 6, 2012

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. Jun 9, 2012

amrah

Prove by mathematical induction that n^3-n is divisible by 2 for all positive integral values of n.

16. Jun 9, 2012

Infinitum

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

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