Simple Induction Problem

• Nov 23rd 2009, 08:56 AM
craig
Simple Induction Problem
Prove by induction that, for all $n \in N$:

$1^3 + 3^3 + 5^3 + ... + (2n - 1)^3 = n^2(2n^2 - 1).$

Prove for $n=1$:

LHS, $1^3 = 1$
RHS, $1^2(2-1)=1$

True for $n=1$, now assume for $n=k$,

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

Now the sequence above is for add numbers, assuming that $k$ is odd, then instead of using $n=k+1$ use $n=k+2$.

We then have:

$1^3 + 3^3 + 5^3 + ... + (2(k+2) - 1)^2$

$1^3 + 3^3 + 5^3 + ... + (2k+4 - 1)^2$

$1^3 + 3^3 + 5^3 + ... + (2k+3)^2$.

Not sure where to go from here? Any help would be great.

Thank you
• Nov 23rd 2009, 09:28 AM
aman_cc
Quote:

Originally Posted by craig
Prove by induction that, for all $n \subset N$:

$1^3 + 3^3 + 5^3 + ... + (2n - 1)^3 = n^2(2n^2 - 1).$

Prove for $n=1$:

LHS, $1^3 = 1$
RHS, $1^2(2-1)=1$

True for $n=1$, now assume for $n=k$,

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

Now the sequence above is for add numbers, assuming that $k$ is odd, then instead of using $n=k+1$ use $n=k+2$.

We then have:

$1^3 + 3^3 + 5^3 + ... + (2(k+2) - 1)^2$

$1^3 + 3^3 + 5^3 + ... + (2k+4 - 1)^2$

$1^3 + 3^3 + 5^3 + ... + (2k+3)^2$.

Not sure where to go from here? Any help would be great.

Thank you

I think the error is in your reasoning for this step:
Now the sequence above is for add numbers, assuming that http://www.mathhelpforum.com/math-he...e8759df3-1.gif is odd, then instead of using http://www.mathhelpforum.com/math-he...4ce9fc8a-1.gif use http://www.mathhelpforum.com/math-he...12d63ee1-1.gif.

even for n=k+1 you will get an odd number. 2k-1 is always odd

else i think the problem should be trivial (i hvn't tried it, but doesn't look too tough)
• Nov 23rd 2009, 11:25 AM
craig
Quote:

Originally Posted by aman_cc
even for n=k+1 you will get an odd number. 2k-1 is always odd

else i think the problem should be trivial (i hvn't tried it, but doesn't look too tough)

I wouldn't for n=k+1, but I see what you mean by using 2k-1, I'll let you know how it goes ;)

• Nov 23rd 2009, 11:34 AM
craig
Have no idea how to do this, it can't be this hard can it haha?

Using $n=2k-1$

$1^3 + 3^3 + 5^3 + ... + (2n - 1)^3 + (2(2k-1)-1)^3$

$1^3 + 3^3 + 5^3 + ... + (2n - 1)^3 + (4k-2-1)^3$

$1^3 + 3^3 + 5^3 + ... + (2n - 1)^3 + (4k-3)^3$

Any pointers would be appreciated :)
• Nov 23rd 2009, 11:56 AM
emakarov
Could you write again carefully your induction hypothesis and what you need to prove? I recommend using k (or n) for the IH, like you did in the first post. Then replace k with k+1 to get what you need to prove.
• Nov 23rd 2009, 12:01 PM
craig
Quote:

Originally Posted by emakarov
Could you write again carefully your induction hypothesis and what you need to prove? I recommend using k (or n) for the IH, like you did in the first post. Then replace k with k+1 to get what you need to prove.

I proved the result was true for n=1

Quote:

Originally Posted by craig
Prove for $n=1$:

LHS, $1^3 = 1$
RHS, $1^2(2-1)=1$

Inductive hypothesis, assume true for $n=k$

Quote:

Originally Posted by craig
True for $n=1$, now assume for $n=k$,

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

The question only involves odd numbers, so wouldn't using $n=k+1$ result in an add number?
• Nov 23rd 2009, 12:09 PM
emakarov
It does not really matter if you noticed or not that it's the sum of cubes of odd numbers. This problem is solved in a completely general way. The problem asks to prove "For all $n\in\mathbb{N}$, $P(n)$", where $P(n)$ is a property of $n$; in this case an equality that contains $n$. The base case is to show $P(1)$, which you have already done. For the induction step, the induction hypothesis is $P(k)$. What you need to show is $P(k+1)$. It makes things much clearer if $P(k)$ and $P(k+1)$ are written explicitly. Note that $P(k+1)$ is obtained from $P(k)$ by replacing $k$ with $k+1$.
• Nov 23rd 2009, 12:23 PM
craig
Thankyou!

Using $n=k+1$, this gives us:

$(1^3 + 3^3 + ... + (2k-1)^3) + (2(k+1)-1)^3$

$(k^2(2k^2-1) + (2k+)^3$

Expanding out the brackets gives us the following quartic:

$2k^4+8k^3+11k^2+6k+1$

Which factorises to give:

$(k+1)^2(2(k+1)^2-1)$

Therefore proof holds for $k+1$ if true for $k$.

Thanks for all the help