Results 1 to 3 of 3

Math Help - Prove recurrence relation equals sum of permutations

  1. #1
    Senior Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    255

    Prove recurrence relation equals sum of permutations

    OK, I am stuck on this MI proof of the following:

    Define a_{0}=1 and for n\geq1, define a_{n}=na_{n-1}+1.
    Prove: For n\geq0  a_{n} = \sum_{j=0}^{n}(n)_{j}.

    First prove the base case for n=0. By definition a_{0}=1. Now show \sum_{j=0}^{0}(0)_{j}=\left(0\right)_{0}=1.

    This proves the base case.

    Now assume a_{k}=ka_{k-1}+1=\sum_{j=0}^{k}(k)_{j}. (IHYP)

    We need to show that a_{k+1}=(k+1)a_{k}+1=\sum_{j=0}^{k+1}(k+1)_{j}.

    I can manipulate the left hand side. What I'm having a problem with is the permutation on the RHS.

    I can take the k+1 term out which gives (k+1)! but I'm still left with the sum of (k+1)_{j}. I can factor out \frac{(k+1)}{(k+1-j)}(k)_{j} but that doesn't seem to make sense either.

    Could someone give me a hint on how to get rid of the (k+1)_{j} in the sum?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by oldguynewstudent View Post
    OK, I am stuck on this MI proof of the following:

    Define a_{0}=1 and for n\geq1, define a_{n}=na_{n-1}+1.
    Prove: For n\geq0  a_{n} = \sum_{j=0}^{n}(n)_{j}.

    First prove the base case for n=0. By definition a_{0}=1. Now show \sum_{j=0}^{0}(0)_{j}=\left(0\right)_{0}=1.

    This proves the base case.

    Now assume a_{k}=ka_{k-1}+1=\sum_{j=0}^{k}(k)_{j}. (IHYP)

    We need to show that a_{k+1}=(k+1)a_{k}+1=\sum_{j=0}^{k+1}(k+1)_{j}.

    I can manipulate the left hand side. What I'm having a problem with is the permutation on the RHS.

    I can take the k+1 term out which gives (k+1)! but I'm still left with the sum of (k+1)_{j}. I can factor out \frac{(k+1)}{(k+1-j)}(k)_{j} but that doesn't seem to make sense either.

    Could someone give me a hint on how to get rid of the (k+1)_{j} in the sum?

    Thanks.
    Hint!

    \sum_{j=0}^{n}(n)_{j}=2^n

    Edit: Is (n)_{j} mean n choose j, {n\choose{j}}?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    255
    Quote Originally Posted by Also sprach Zarathustra View Post
    Hint!

    \sum_{j=0}^{n}(n)_{j}=2^n

    Edit: Is (n)_{j} mean n choose j, {n\choose{j}}?
    (n)_{j} is nPj or the j permutaions of n objects. Or the number of j lists without repetition from an n-set.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. prove that recurrence relation is odd
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 14th 2011, 02:24 AM
  2. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 24th 2011, 04:12 AM
  3. Replies: 0
    Last Post: April 13th 2010, 08:48 PM
  4. Prove limit of recurrence relation
    Posted in the Calculus Forum
    Replies: 2
    Last Post: April 1st 2007, 12:57 PM
  5. Replies: 4
    Last Post: November 12th 2006, 05:09 PM

Search Tags


/mathhelpforum @mathhelpforum