Results 1 to 5 of 5

Math Help - Constructive Induction

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    9

    Constructive Induction

    I am trying to solve a problem with Constructive Induction. But I really don't understand what Constructive Induction is. Can anyone explain it to me using the following problem as an example? Thanks

    Problem:
    Use constructive induction to derive a formula for the following:
    n
    Σ i^(3)
    i=1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by tshare1 View Post
    I am trying to solve a problem with Constructive Induction. But I really don't understand what Constructive Induction is. Can anyone explain it to me using the following problem as an example? Thanks

    Problem:
    Use constructive induction to derive a formula for the following:
    n
    Σ i^(3)
    i=1
    The formula you gave makes no sense for induction. There is noting to induce or deduce.

    \Sigma_{i=1}^N i^3 is equal to i^3 \Sigma_{i=1}^n=n i^3
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by tshare1 View Post
    I am trying to solve a problem with Constructive Induction. But I really don't understand what Constructive Induction is. Can anyone explain it to me using the following problem as an example? Thanks

    Problem:
    Use constructive induction to derive a formula for the following:
    n
    Σ i^(3)
    i=1
    n=1: \sum_{1=1}^1i^3=1^3=1

    n=2: \sum_{i=1}^2i^3=1+2^3=1+8=9

    n=3: \sum_{i=1}^3i^3=9+3^3=9+27=36

    n=4: \sum_{i=1}^4i^3=36+4^3=36+64=100

    n=5: \sum_{i=1}^5i^3=100+5^3=100+125=225

    Pattern

    1, 9, 36, 100, 225.... are squares

    1=1^2,\ 9=3^2,\ 36=6^2,\ 100=10^2,\ 225=15^2,....

    Pattern

    The numbers that are squared differ by "n" each time.

    n=1: 1=1

    n=2: 3=1+2

    n=3: 6=1+2+3

    n=4: 10=1+2+3+4

    n=5: 15=1+2+3+4+5

    Hypothesis: \sum_{i=1}^ni^3=\left(\sum_{i=1}^ni\right)^2

    Sum of the cubes of n consecutive natural numbers=the square of the sum of the n numbers.


    \sum_{i=1}^ni=\frac{n(n+1)}{2}

    \sum_{i=1}^ni^3=\left(\frac{n(n+1)}{2}\right)^2=\f  rac{n^2(n+1)^2}{4}
    Last edited by Archie Meade; February 14th 2010 at 10:03 AM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Of course, that is not the complete proof.
    The formula has been derived by examining a pattern from the first few terms of n.

    To be sure whether this formula holds for all n natural numbers,
    we try to establish that the formula being true for some n=k, causes the formula to be true for the next n=k+1.

    Because we use n or k, we are attempting to establish this term-by-term relationship in general for all pairs of terms.

    If it works then a chain-reaction is established for all n.

    To do this we try to prove

    \sum_{i=1}^{k+1}i^3=\frac{(k+1)^2(k+2)^2}{4}

    Therefore, we start by adding the next cube

    (k+1)^3+\frac{k^2(k+1)^2}{4}=(k+1)(k+1)^2+\frac{k^  2(k+1)^2}{4}

    =\frac{(k+1)^2\left(4(k+1)+k^2\right)}{4}=\frac{(k  +1)^2(4k+4+k^2)}{4}=\frac{(k+1)^2(k+2)^2}{4}

    Therefore the formula holds for all n, as it holds for n=1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Archie Meade View Post
    Of course, that is not the complete proof.
    The formula has been derived by examining a pattern from the first few terms of n.

    To be sure whether this formula holds for all n natural numbers,
    we try to establish that the formula being true for some n=k, causes the formula to be true for the next n=k+1.

    Because we use n or k, we are attempting to establish this term-by-term relationship in general for all pairs of terms.

    If it works then a chain-reaction is established for all n.

    To do this we try to prove

    \sum_{i=1}^{k+1}i^3=\frac{(k+1)^2(k+2)^2}{4}

    Therefore, we start by adding the next cube

    (k+1)^3+\frac{k^2(k+1)^2}{4}=(k+1)(k+1)^2+\frac{k^  2(k+1)^2}{4}

    =\frac{(k+1)^2\left(4(k+1)+k^2\right)}{4}=\frac{(k  +1)^2(4k+4+k^2)}{4}=\frac{(k+1)^2(k+2)^2}{4}

    Therefore the formula holds for all n, as it holds for n=1.
    You are right.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. constructive proof
    Posted in the Calculus Forum
    Replies: 3
    Last Post: September 21st 2010, 08:47 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. constructive method of proving algebraic closure?
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: May 21st 2010, 06:58 PM
  4. Constructive Proof Homework
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 1st 2009, 09:45 PM
  5. Replies: 2
    Last Post: May 14th 2008, 08:56 AM

Search Tags


/mathhelpforum @mathhelpforum