Page 1 of 2 12 LastLast
Results 1 to 15 of 17
Like Tree6Thanks

Math Help - Proving by induction help

  1. #1
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    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.

    Proving by induction help-proveby-induction.png
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121

    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.
    Thanks from jpab29
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    537
    Thanks
    216

    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.
    Last edited by johng; July 11th 2013 at 04:27 PM.
    Thanks from jpab29
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,546
    Thanks
    539

    Re: Proving by induction help

    Hello, jpab29!

    There must be typo . . .


    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}
    Thanks from jpab29
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Re: Proving by induction help

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

    Proving by induction help-conjecture-hw.png

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

    Proving by induction help-conjecture-1.png
    Proving by induction help-conjecture-2.png
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    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.
    Thanks from jpab29
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Re: Proving by induction help

    Thanks so much, yes I'll need a walkthrough
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Proving by induction help

    Quote Originally Posted by jpab29 View Post
    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?
    Last edited by MarkFL; July 11th 2013 at 07:58 PM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    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.

    Proving by induction help-plugging-ns.jpg

    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    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
    Thanks from jpab29
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Jul 2013
    From
    California
    Posts
    56

    Re: Proving by induction help

    Proving by induction help-leftside.jpgClick image for larger version. 

Name:	leftside.jpg 
Views:	3 
Size:	982.2 KB 
ID:	28799

    Thank you so much!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    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.
    Thanks from jpab29
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Proving by Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2012, 05:30 PM
  2. Proving by induction
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: November 17th 2012, 02:42 PM
  3. Proving by induction
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 23rd 2012, 10:16 PM
  4. proving (by induction)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 30th 2009, 04:50 PM
  5. Need help proving!! Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 06:38 PM

Search Tags


/mathhelpforum @mathhelpforum