# Proving by induction help

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Jul 11th 2013, 04:29 PM
jpab29
Proving by induction help
Can this be proven by induction? Because I really can't.

I come down to

k^3 - 3k^2 + 5k = 2k^3 + 3k^ + 3k + 1 which is not equal. :( thanks.

Attachment 28783
• Jul 11th 2013, 05:12 PM
HallsofIvy
Re: Proving by induction help
You are trying to prove that $\sum_{i=1}^n (2i- 1)= (n- 1)^3+ n^3$?

Your fundamental problem is that this isn't true!

When n= 2, $\sum_{i= 1}^2 (2i- 1)= (2(1)- 1)+ (2(2)-1)= 1+ 3= 4$ while $(2- 1)^3+ 2^3= 1+ 8= 9$.
• Jul 11th 2013, 05:14 PM
johng
Re: Proving by induction help
Hi,
"Plug in" n = 1. This then reads 1 = 1, good so far. Next try n = 2: 1 + 3 = 13 + 23, which is of course false. So your formula is not true for all n and so certainly can't be proved by induction.

$\sum_{i=1}^n2i-1=n^2$

The above is the correct formula and can be proved by induction. I suggest you try it.

Edit:
It suddenly occurred to me that you probably copied the problem incorrectly. What is true:

$\sum_{i=1}^n(2i-1)^2=(n-1)^3+n^3$

This formula is amenable to induction. Try it.
• Jul 11th 2013, 05:31 PM
Soroban
Re: Proving by induction help
Hello, jpab29!

There must be typo . . .

Quote:

Can this be proven by induction? . No!

. . $\displaystyle \sum^n_{i=1}(2i-1) \;=\;(n-1)^3 + n^3$ . This is not true!

$\text{Fact: }\;\sum^n_{i=1}(2i-1) \;=\;1 + 3 + 5 + \cdots + (2n-1) \;=\;{\color{blue}n^2}$
• Jul 11th 2013, 07:22 PM
jpab29
Re: Proving by induction help
oh that's why. haha Actually it is derived from a conjecture that I am working on.

http://mathhelpforum.com/discrete-ma...induction.html
• Jul 11th 2013, 07:24 PM
jpab29
Re: Proving by induction help
Thank you so much for taking the time! I actually have no idea how to work it out. I am taking math class online and it's terrible, no help at all, except from forums like these. I'll try the edit that you've made.
• Jul 11th 2013, 07:28 PM
jpab29
Re: Proving by induction help
This is what I'm trying to work on and also trying to understand it through internet's help. :(

Attachment 28790

This is the book example i'm trying to follow.

Attachment 28791
Attachment 28792
• Jul 11th 2013, 07:31 PM
MarkFL
Re: Proving by induction help
As I posted at MMF, the conjecture you want is:

$\sum_{k=0}^{2(n-1)}$$n^2-2n+2+k$$=(n-1)^3+n^3$

edit: If you want, I can walk you through how I came up with it. :D
• Jul 11th 2013, 07:43 PM
jpab29
Re: Proving by induction help
oh okay, so the 2n-1 with the summation sign is not a constant formula? it changes? So sorry about being clueless. The book only gives one example per kind of question. :(
• Jul 11th 2013, 07:47 PM
jpab29
Re: Proving by induction help
Thanks so much, yes I'll need a walkthrough :) :) :)
• Jul 11th 2013, 08:16 PM
MarkFL
Re: Proving by induction help
Quote:

Originally Posted by jpab29
Thanks so much, yes I'll need a walkthrough :) :) :)

This is what I noticed:

For each line 1) - 4) (and letting the line number be $n$), I noticed that the first number in the sum is:

$(n-1)^2+1=n^2-2n+2$

Now, we then are adding the next $2n-2=2(n-1)$ consecutive integers. As you observed, the sum is shown to be equal to $(n-1)^3+n^3$. So, we may state this as:

$\sum_{k=0}^{2(n-1)}(n^2-2n+2+k)=(n-1)^3+n^3$

Does this make sense?
• Jul 11th 2013, 08:42 PM
jpab29
Re: Proving by induction help
I still only understood (n-1)^3 + n^3...

But I don't get the left side still... how it evolved. But I tried plugging the N's.

Attachment 28796

:(
• Jul 11th 2013, 08:57 PM
MarkFL
Re: Proving by induction help
Using the conjecture I stated originally (I had a typo the second time...):

$\sum_{k=0}^{2(n-1)}(n^2-2n+2+k)=(n-1)^3+n^3$

We have for:

$n=1$

$\sum_{k=0}^{2(1-1)}(1^2-2(1)+2+k)=(1-1)^3+1^3$

$1=0^3+1^3$

$n=2$

$\sum_{k=0}^{2(2-1)}(2^2-2(2)+2+k)=(2-1)^3+2^3$

$2+3+4=1^3+2^3$

$n=3$

$\sum_{k=0}^{2(3-1)}(3^2-2(3)+2+k)=(3-1)^3+3^3$

$5+6+7+8+9=2^3+3^3$

$n=4$

$\sum_{k=0}^{2(4-1)}(4^2-2(4)+2+k)=(4-1)^3+4^3$

$10+11+12+13+14+15+16=3^3+4^3$
• Jul 11th 2013, 09:35 PM
jpab29
Re: Proving by induction help
• Jul 11th 2013, 10:07 PM
MarkFL
Re: Proving by induction help
If I was going to prove this by induction, this is what I would do. We have already shown the base case $P_1$ is true, so the induction hypothesis $P_n$ is the so-called conjecture:

$\sum_{k=0}^{2(n-1)}(n^2-2n+2+k)=(n-1)^3+n^3$

Let's simplify a bit:

$\sum_{k=0}^{2(n-1)}(n^2-2n+2)+\sum_{k=0}^{2(n-1)}(k)=(n-1)^3+n^3$

$(2n-1)(n^2-2n+2)+\sum_{k=0}^{2(n-1)}(k)=(n-1)^3+n^3$

$2n^3-5n^2+6n-2+\sum_{k=0}^{2(n-1)}(k)=2n^3-3n^2+3n-1$

$\sum_{k=0}^{2(n-1)}(k)=2n^2-3n+1$

As the inductive step, I would add $2n-1+2n=4n-1$:

$\sum_{k=0}^{2((n+1)-1)}(k)=2n^2+n=2(n+1)^2-3(n+1)+1$

We have derived $P_{n+1}$ from $P_n$ thereby completing the proof by induction.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last