Results 1 to 3 of 3

Thread: 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 $\displaystyle a_{0}=1$ and for $\displaystyle n\geq1$, define $\displaystyle a_{n}=na_{n-1}+1$.
    Prove: For $\displaystyle n\geq0 a_{n} = \sum_{j=0}^{n}(n)_{j}$.

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

    This proves the base case.

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

    We need to show that $\displaystyle 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 $\displaystyle (k+1)_{j}$. I can factor out $\displaystyle \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 $\displaystyle (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 $\displaystyle a_{0}=1$ and for $\displaystyle n\geq1$, define $\displaystyle a_{n}=na_{n-1}+1$.
    Prove: For $\displaystyle n\geq0 a_{n} = \sum_{j=0}^{n}(n)_{j}$.

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

    This proves the base case.

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

    We need to show that $\displaystyle 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 $\displaystyle (k+1)_{j}$. I can factor out $\displaystyle \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 $\displaystyle (k+1)_{j}$ in the sum?

    Thanks.
    Hint!

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

    Edit: Is $\displaystyle (n)_{j}$ mean n choose j, $\displaystyle {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!

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

    Edit: Is $\displaystyle (n)_{j}$ mean n choose j, $\displaystyle {n\choose{j}}$?
    $\displaystyle (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: Sep 14th 2011, 02:24 AM
  2. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 24th 2011, 04:12 AM
  3. Replies: 0
    Last Post: Apr 13th 2010, 08:48 PM
  4. Prove limit of recurrence relation
    Posted in the Calculus Forum
    Replies: 2
    Last Post: Apr 1st 2007, 12:57 PM
  5. Replies: 4
    Last Post: Nov 12th 2006, 05:09 PM

Search Tags


/mathhelpforum @mathhelpforum