Results 1 to 3 of 3

Math Help - Solve the recurrence relation

  1. #1
    Super Member
    Joined
    Jan 2009
    Posts
    715

    Solve the recurrence relation

    Solve the recurrence relation


     \sum_{k=1}^n \binom{n}{k} a(k) = \frac{n}{n+1}

    I have two methods, one is general , by looking at first few terms and prove my deduction by induction .

    I want to discuss the second one , I construct

     a(k) = c \int_0^1 [f(t)]^k~dt so we have

     c \int_0^1 \sum_{k=1}^n \binom{n}{k} [f(t)]^k~dt = \frac{n}{n+1}

     c \int_0^1 ( [ 1 + f(t)]^n - 1) ~dt = \frac{n}{n+1}

    Let  c=-1 , then we obtain

     \int_0^1 [ 1 + f(t)]^n ~dt = \frac{1}{n+1}

    I know that  \int_0^1 t^n ~dt = \frac{1}{n+1}


    so i let  1 + f(t) = t and i find that

     a(k) = -\int_0^1 (t-1)^k~dt = \frac{(-1)^{k+1}}{k+1}

    My problem is since  \int_0^1 [g(t)]^n~dt = \frac{1}{n+1} has many solutions , if we choose other solution , will we arrive at the same destination ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by simplependulum View Post
    My problem is since  \int_0^1 [g(t)]^n~dt = \frac{1}{n+1} has many solutions , if we choose other solution , will we arrive at the same destination ?
    Yes, for a fixed n. But how many satisfy that for all n\in \mathbb{N} ?

    It's true that if you have one such function then it generates a solution. -and well, in this case you can check that each a(k) is unique, once you you have found a function like that, you are done. But on a different problem -another recurrence- there might not be a function satisfying a(k)=c\cdot \int_0^1\{f(t)\}^kdt.

    About the original equation, if you have 2 e.g.f s (exponential generating functions) A(x) and B(x) -generated by a_k and b_k respectively-, then A(x)\cdot B( x) = \sum_{n=0}^{\infty}\left(\sum_{k=0}^n\binom{n}{k}\  cdot a_k \cdot b_{n-k}\right)\cdot \tfrac{x^n}{n!}. In your case pick B(x)=e^x - note that a(0)=0 ...-
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member Renji Rodrigo's Avatar
    Joined
    Sep 2009
    From
    Rio de janeiro
    Posts
    38
    Other solution

    iff you have something like

     \sum^n_{k=0} {n \choose k}a(k) =f(n)

    then

     a(k)=\Delta^k f(0)
    where  \Delta^k f(0) is the difference operator

    \Delta^0 f(x) =f(x)
     \Delta^{n+1} f(x)= \Delta^n f(x+1)-\Delta^n f(x)
    for all n in N.

    It's Newton interpolation formula
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 16th 2010, 01:56 AM
  2. Solve the recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 10th 2010, 05:16 AM
  3. Recurrence Relation Q
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 30th 2009, 11:57 PM
  4. How to solve this recurrence relation ?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 19th 2009, 04:31 PM
  5. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum