Results 1 to 3 of 3

Thread: Solve the recurrence relation

  1. #1
    Super Member
    Joined
    Jan 2009
    Posts
    715

    Solve the recurrence relation

    Solve the recurrence relation


    $\displaystyle \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

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

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

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

    Let $\displaystyle c=-1 $ , then we obtain

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

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


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

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

    My problem is since $\displaystyle \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 $\displaystyle \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 $\displaystyle n$. But how many satisfy that for all $\displaystyle 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 $\displaystyle 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 $\displaystyle 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) $\displaystyle A(x)$ and $\displaystyle B(x)$ -generated by $\displaystyle a_k$ and $\displaystyle b_k$ respectively-, then $\displaystyle 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 $\displaystyle B(x)=e^x$ - note that $\displaystyle 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

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

    then

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

    $\displaystyle \Delta^0 f(x) =f(x)$
    $\displaystyle \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: Nov 16th 2010, 01:56 AM
  2. Solve the recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Sep 10th 2010, 05:16 AM
  3. Recurrence Relation Q
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 30th 2009, 11:57 PM
  4. How to solve this recurrence relation ?
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Apr 19th 2009, 04:31 PM
  5. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 15th 2009, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum