# Simple Induction Problem

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

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

Prove for $\displaystyle n=1$:

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

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

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

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

We then have:

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

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

$\displaystyle 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 $\displaystyle n \subset N$:

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

Prove for $\displaystyle n=1$:

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

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

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

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

We then have:

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

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

$\displaystyle 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 $\displaystyle n=2k-1$

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

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

$\displaystyle 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 $\displaystyle n=1$:

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

Inductive hypothesis, assume true for $\displaystyle n=k$

Quote:

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

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

The question only involves odd numbers, so wouldn't using $\displaystyle 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 $\displaystyle n\in\mathbb{N}$, $\displaystyle P(n)$", where $\displaystyle P(n)$ is a property of $\displaystyle n$; in this case an equality that contains $\displaystyle n$. The base case is to show $\displaystyle P(1)$, which you have already done. For the induction step, the induction hypothesis is $\displaystyle P(k)$. What you need to show is $\displaystyle P(k+1)$. It makes things much clearer if $\displaystyle P(k)$ and $\displaystyle P(k+1)$ are written explicitly. Note that $\displaystyle P(k+1)$ is obtained from $\displaystyle P(k)$ by replacing $\displaystyle k$ with $\displaystyle k+1$.
• Nov 23rd 2009, 12:23 PM
craig
Thankyou!

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

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

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

Expanding out the brackets gives us the following quartic:

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

Which factorises to give:

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

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

Thanks for all the help