Results 1 to 4 of 4

Math Help - Don't know what to do here, recursive problem

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    20

    Don't know what to do here, recursive problem

    The succession [Xsubn] is defined as

    Xsub0 = 0, Xsub(n+1) = Xsubn + n(n+1)

    Show that Xsubn = (1/3)(n-1)n(n+1).

    I am assuming I am not allowed to use what I am demonstring as part of the proof. No clue what do despite staring at it for 15 minutes.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    Hi,

    x_0 = 0, x_{n+1} = x_n + n(n+1)
    and we have to prove x_n = \frac{1}{3}(n-1)n(n+1).

    We proceed by induction:
    n=0 .. x_0 = \frac{1}{3}(0-1)\cdot 0\cdot (0+1) =0 so the base case holds.

    suppose the statement holds for n and let's prove it holds for n+1:
    x_{n+1}= x_n + n(n+1) = \frac{1}{3}(n-1)n(n+1) +n(n+1) (by induction hypotheses)
    = n(n+1)(\frac{1}{3}(n-1)+1) = n(n+1)(\frac{1}{3}n+\frac{2}{3}) = \frac{1}{3}n(n+1)(n+2)
    =\frac{1}{3}((n+1)-1)(n+1)((n+1)+1) so the inductive step is done.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    20
    My mistake was thinking you can't use the statement your trying to prove. But with induction you can. Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,405
    Thanks
    1328

    Angry

    But it is perfectly valid to show that what you are given is a solution to an equation by putting it into the equation.

    For example, it would be very difficult to solve x^5- 6x^2- 3x- 2= 0 but it is very easy to show that x= 2 is a solutions: [tex]2^2- 6(2^2)- 3(2)- 6= 32- 24- 6- 2= 0.

    Similarly, here, you are not asked to solve the recursion, just to show that x_n= \frac{(n-1)n(n+1)}{3} satisfies it. And that is basically what Taluivren did.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: April 27th 2010, 07:57 AM
  2. A Recursive Function Problem in Mathematica
    Posted in the Math Software Forum
    Replies: 2
    Last Post: July 1st 2009, 02:20 PM
  3. Primitive Recursive vs Recursive Functions
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 29th 2009, 07:32 AM
  4. Recursive Deinition of order pairs problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 5th 2008, 12:45 PM
  5. self-contradictory recursive problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 26th 2008, 09:41 AM

Search Tags


/mathhelpforum @mathhelpforum