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

Printable View

- Jul 11th 2013, 03:29 PMjpab29Proving 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, 04:12 PMHallsofIvyRe: Proving by induction help
You are trying to prove that $\displaystyle \sum_{i=1}^n (2i- 1)= (n- 1)^3+ n^3$?

Your fundamental problem is that this**isn't true**!

When n= 2, $\displaystyle \sum_{i= 1}^2 (2i- 1)= (2(1)- 1)+ (2(2)-1)= 1+ 3= 4$ while $\displaystyle (2- 1)^3+ 2^3= 1+ 8= 9$. - Jul 11th 2013, 04:14 PMjohngRe: Proving by induction help
Hi,

"Plug in" n = 1. This then reads 1 = 1, good so far. Next try n = 2: 1 + 3 = 1^{3}+ 2^{3}, which is of course false. So your formula is not true for all n and so certainly can't be proved by induction.

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

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

This formula is amenable to induction. Try it. - Jul 11th 2013, 04:31 PMSorobanRe: Proving by induction help
Hello, jpab29!

There must be typo . . .

Quote:

Can this be proven by induction? . No!

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

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

It is from this link.

http://mathhelpforum.com/discrete-ma...induction.html - Jul 11th 2013, 06:24 PMjpab29Re: 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, 06:28 PMjpab29Re: 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, 06:31 PMMarkFLRe: Proving by induction help
As I posted at MMF, the conjecture you want is:

$\displaystyle \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, 06:43 PMjpab29Re: 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, 06:47 PMjpab29Re: Proving by induction help
Thanks so much, yes I'll need a walkthrough :) :) :)

- Jul 11th 2013, 07:16 PMMarkFLRe: Proving by induction help
This is what I noticed:

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

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

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

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

Does this make sense? - Jul 11th 2013, 07:42 PMjpab29Re: 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, 07:57 PMMarkFLRe: Proving by induction help
Using the conjecture I stated originally (I had a typo the second time...):

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

We have for:

$\displaystyle n=1$

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

$\displaystyle 1=0^3+1^3$

$\displaystyle n=2$

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

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

$\displaystyle n=3$

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

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

$\displaystyle n=4$

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

$\displaystyle 10+11+12+13+14+15+16=3^3+4^3$ - Jul 11th 2013, 08:35 PMjpab29Re: Proving by induction help
Attachment 28799Attachment 28799

Thank you so much! - Jul 11th 2013, 09:07 PMMarkFLRe: 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 $\displaystyle P_1$ is true, so the induction hypothesis $\displaystyle P_n$ is the so-called conjecture:

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

Let's simplify a bit:

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

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

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

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

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

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

We have derived $\displaystyle P_{n+1}$ from $\displaystyle P_n$ thereby completing the proof by induction.