# 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.