# Thread: Proving by induction help

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

2. ## Re: 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$.

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

$\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.

4. ## Re: Proving by induction help

Hello, jpab29!

There must be typo . . .

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}$

5. ## Re: 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.

Mathematical Induction

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

7. ## Re: Proving by induction help

This is what I'm trying to work on and also trying to understand it through internet's help.

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

8. ## Re: 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.

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

10. ## Re: Proving by induction help

Thanks so much, yes I'll need a walkthrough

11. ## Re: Proving by induction help

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 $\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?

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

13. ## Re: 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$

14. ## Re: Proving by induction help

Thank you so much!

15. ## 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 $\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.

Page 1 of 2 12 Last