Inverting the binomial convolution of sequences












3












$begingroup$


let $left { a_{n} right }_{n=0}^{infty}$ and $left { b_{n} right }_{n=0}^{infty}$ be two sequences. The binomial convolution of the two sequences is given by :
$$left(astar bright)_{n}=c_{n}=sum_{k=0}^{n}binom{n}{k}a_{k}b_{n-k}$$
Is there a way to recover $a_{n}b_{n}$ via something akin to :
$$a_{n}b_{n}=sum_{k=0}^{n}d_{n,k}c_{k}$$










share|cite|improve this question









$endgroup$

















    3












    $begingroup$


    let $left { a_{n} right }_{n=0}^{infty}$ and $left { b_{n} right }_{n=0}^{infty}$ be two sequences. The binomial convolution of the two sequences is given by :
    $$left(astar bright)_{n}=c_{n}=sum_{k=0}^{n}binom{n}{k}a_{k}b_{n-k}$$
    Is there a way to recover $a_{n}b_{n}$ via something akin to :
    $$a_{n}b_{n}=sum_{k=0}^{n}d_{n,k}c_{k}$$










    share|cite|improve this question









    $endgroup$















      3












      3








      3


      2



      $begingroup$


      let $left { a_{n} right }_{n=0}^{infty}$ and $left { b_{n} right }_{n=0}^{infty}$ be two sequences. The binomial convolution of the two sequences is given by :
      $$left(astar bright)_{n}=c_{n}=sum_{k=0}^{n}binom{n}{k}a_{k}b_{n-k}$$
      Is there a way to recover $a_{n}b_{n}$ via something akin to :
      $$a_{n}b_{n}=sum_{k=0}^{n}d_{n,k}c_{k}$$










      share|cite|improve this question









      $endgroup$




      let $left { a_{n} right }_{n=0}^{infty}$ and $left { b_{n} right }_{n=0}^{infty}$ be two sequences. The binomial convolution of the two sequences is given by :
      $$left(astar bright)_{n}=c_{n}=sum_{k=0}^{n}binom{n}{k}a_{k}b_{n-k}$$
      Is there a way to recover $a_{n}b_{n}$ via something akin to :
      $$a_{n}b_{n}=sum_{k=0}^{n}d_{n,k}c_{k}$$







      combinatorics






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Dec 20 '18 at 13:11









      Mohammad Al JamalMohammad Al Jamal

      174321




      174321






















          3 Answers
          3






          active

          oldest

          votes


















          1












          $begingroup$

          Let





          • $a_n=1$,


          • $b_n=1$,


          • $tilde a_n=2^n$, and


          • $tilde b_0=1$, $tilde b_n=0$ for all $n>0$.


          Note that $$a_nstar b_n=tilde a_nstar tilde b_n=2^n$$ have the same binomial convolution, but $$a_nb_n=1neq tilde b_n=tilde a_ntilde b_n.$$ Therefore, the binomial convolution is insufficient to recover the Hadamard product.






          share|cite|improve this answer









          $endgroup$





















            1












            $begingroup$

            Edit: this does not answer the question (see comments.)



            Let $X$ be the space of all (real or complex) sequences $a={a_n}_0^infty$ and define $Tcolon Xto X$ as
            $$
            (Ta)_n=sum_{k=0}^nbinom{n}{k}a_k.
            $$

            What you are asking is if $a$ can be recovered from $Ta$. The answer is yes, and it can be done recursively. First of all, it is clear that $a_0=(Ta)_0$. Now, if $a_0,dots,a_{n-1}$ have been found, we have
            $$
            a_n=(Ta)_n-sum_{k=0}^{n-1}binom{n}{k}a_k.
            $$






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
              $endgroup$
              – Mike Earnest
              Dec 20 '18 at 18:15










            • $begingroup$
              I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
              $endgroup$
              – Julián Aguirre
              Dec 20 '18 at 19:02



















            1












            $begingroup$

            Given
            $$
            c_{,n} = ,sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k} a_{,k} ,b_{,n - k} }
            $$

            then notice that the e.g.f.'s are in the following relation
            $$
            eqalign{
            & C(z) = sumlimits_{0, le ,n,} {{{c_{,n} } over {n!}},z^{,n} }
            = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
            a_{,k} ,b_{,n - k} ,z^{,n} } } = cr
            & = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
            a_{,k} z^{,k} ,b_{,n - k} z^{,n - k} ,} } = cr
            & = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {{{a_{,k} } over {k!}}z^{,k}
            ,{{b_{,n - k} } over {left( {n - k} right)!}}z^{,n - k} ,} } = cr
            & = ,left( {sumlimits_{0, le ,n,} {{{a_{,k} } over {k!}}z^{,k} } } right)left( {sumlimits_{0, le ,j,} {,{{b_{,j} } over {j!}}z^{,j} ,} } right) = cr
            & = ,A(z)B(z) cr}
            $$



            That premised, and passing for simplicity to the ordinary g.f.
            $$
            C(z) = sumlimits_{0, le ,n,} {c_{,n} ,z^{,n} }
            = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {a_{,k} ,b_{,n - k} ,z^{,n} } } = A(z)B(z)
            $$

            if I understand properly your question and comment, you need to compute $D(z)$
            $$
            D(z) = sumlimits_{0, le ,n,} {a_{,n} b_{,n} ,z^{,n} }
            $$

            knowing $A(z)$ and $B(z)$ .



            Then, assuming that these are convergent in a domain of non-null measure, you can use the
            duality of the Convolution Theorem , same as for the Fourier series, which for the z-Transform
            reads as
            $$
            D(z) = {1 over {i2pi }}ointlimits_C {A(z)B(z/v){{dv} over v}}
            $$

            refer to last entry of the table in this Wikipedia Article






            share|cite|improve this answer











            $endgroup$









            • 1




              $begingroup$
              yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
              $endgroup$
              – Mohammad Al Jamal
              Dec 20 '18 at 21:42












            • $begingroup$
              @MohammadAlJamal: added possible solution: don't know if I caught exactly your question
              $endgroup$
              – G Cab
              Dec 21 '18 at 0:41






            • 2




              $begingroup$
              $sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
              $endgroup$
              – reuns
              Dec 21 '18 at 1:20













            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "69"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047527%2finverting-the-binomial-convolution-of-sequences%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            3 Answers
            3






            active

            oldest

            votes








            3 Answers
            3






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            1












            $begingroup$

            Let





            • $a_n=1$,


            • $b_n=1$,


            • $tilde a_n=2^n$, and


            • $tilde b_0=1$, $tilde b_n=0$ for all $n>0$.


            Note that $$a_nstar b_n=tilde a_nstar tilde b_n=2^n$$ have the same binomial convolution, but $$a_nb_n=1neq tilde b_n=tilde a_ntilde b_n.$$ Therefore, the binomial convolution is insufficient to recover the Hadamard product.






            share|cite|improve this answer









            $endgroup$


















              1












              $begingroup$

              Let





              • $a_n=1$,


              • $b_n=1$,


              • $tilde a_n=2^n$, and


              • $tilde b_0=1$, $tilde b_n=0$ for all $n>0$.


              Note that $$a_nstar b_n=tilde a_nstar tilde b_n=2^n$$ have the same binomial convolution, but $$a_nb_n=1neq tilde b_n=tilde a_ntilde b_n.$$ Therefore, the binomial convolution is insufficient to recover the Hadamard product.






              share|cite|improve this answer









              $endgroup$
















                1












                1








                1





                $begingroup$

                Let





                • $a_n=1$,


                • $b_n=1$,


                • $tilde a_n=2^n$, and


                • $tilde b_0=1$, $tilde b_n=0$ for all $n>0$.


                Note that $$a_nstar b_n=tilde a_nstar tilde b_n=2^n$$ have the same binomial convolution, but $$a_nb_n=1neq tilde b_n=tilde a_ntilde b_n.$$ Therefore, the binomial convolution is insufficient to recover the Hadamard product.






                share|cite|improve this answer









                $endgroup$



                Let





                • $a_n=1$,


                • $b_n=1$,


                • $tilde a_n=2^n$, and


                • $tilde b_0=1$, $tilde b_n=0$ for all $n>0$.


                Note that $$a_nstar b_n=tilde a_nstar tilde b_n=2^n$$ have the same binomial convolution, but $$a_nb_n=1neq tilde b_n=tilde a_ntilde b_n.$$ Therefore, the binomial convolution is insufficient to recover the Hadamard product.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Dec 22 '18 at 5:25









                Mike EarnestMike Earnest

                23.3k12051




                23.3k12051























                    1












                    $begingroup$

                    Edit: this does not answer the question (see comments.)



                    Let $X$ be the space of all (real or complex) sequences $a={a_n}_0^infty$ and define $Tcolon Xto X$ as
                    $$
                    (Ta)_n=sum_{k=0}^nbinom{n}{k}a_k.
                    $$

                    What you are asking is if $a$ can be recovered from $Ta$. The answer is yes, and it can be done recursively. First of all, it is clear that $a_0=(Ta)_0$. Now, if $a_0,dots,a_{n-1}$ have been found, we have
                    $$
                    a_n=(Ta)_n-sum_{k=0}^{n-1}binom{n}{k}a_k.
                    $$






                    share|cite|improve this answer











                    $endgroup$













                    • $begingroup$
                      I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
                      $endgroup$
                      – Mike Earnest
                      Dec 20 '18 at 18:15










                    • $begingroup$
                      I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
                      $endgroup$
                      – Julián Aguirre
                      Dec 20 '18 at 19:02
















                    1












                    $begingroup$

                    Edit: this does not answer the question (see comments.)



                    Let $X$ be the space of all (real or complex) sequences $a={a_n}_0^infty$ and define $Tcolon Xto X$ as
                    $$
                    (Ta)_n=sum_{k=0}^nbinom{n}{k}a_k.
                    $$

                    What you are asking is if $a$ can be recovered from $Ta$. The answer is yes, and it can be done recursively. First of all, it is clear that $a_0=(Ta)_0$. Now, if $a_0,dots,a_{n-1}$ have been found, we have
                    $$
                    a_n=(Ta)_n-sum_{k=0}^{n-1}binom{n}{k}a_k.
                    $$






                    share|cite|improve this answer











                    $endgroup$













                    • $begingroup$
                      I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
                      $endgroup$
                      – Mike Earnest
                      Dec 20 '18 at 18:15










                    • $begingroup$
                      I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
                      $endgroup$
                      – Julián Aguirre
                      Dec 20 '18 at 19:02














                    1












                    1








                    1





                    $begingroup$

                    Edit: this does not answer the question (see comments.)



                    Let $X$ be the space of all (real or complex) sequences $a={a_n}_0^infty$ and define $Tcolon Xto X$ as
                    $$
                    (Ta)_n=sum_{k=0}^nbinom{n}{k}a_k.
                    $$

                    What you are asking is if $a$ can be recovered from $Ta$. The answer is yes, and it can be done recursively. First of all, it is clear that $a_0=(Ta)_0$. Now, if $a_0,dots,a_{n-1}$ have been found, we have
                    $$
                    a_n=(Ta)_n-sum_{k=0}^{n-1}binom{n}{k}a_k.
                    $$






                    share|cite|improve this answer











                    $endgroup$



                    Edit: this does not answer the question (see comments.)



                    Let $X$ be the space of all (real or complex) sequences $a={a_n}_0^infty$ and define $Tcolon Xto X$ as
                    $$
                    (Ta)_n=sum_{k=0}^nbinom{n}{k}a_k.
                    $$

                    What you are asking is if $a$ can be recovered from $Ta$. The answer is yes, and it can be done recursively. First of all, it is clear that $a_0=(Ta)_0$. Now, if $a_0,dots,a_{n-1}$ have been found, we have
                    $$
                    a_n=(Ta)_n-sum_{k=0}^{n-1}binom{n}{k}a_k.
                    $$







                    share|cite|improve this answer














                    share|cite|improve this answer



                    share|cite|improve this answer








                    edited Dec 20 '18 at 19:03

























                    answered Dec 20 '18 at 14:52









                    Julián AguirreJulián Aguirre

                    69k24096




                    69k24096












                    • $begingroup$
                      I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
                      $endgroup$
                      – Mike Earnest
                      Dec 20 '18 at 18:15










                    • $begingroup$
                      I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
                      $endgroup$
                      – Julián Aguirre
                      Dec 20 '18 at 19:02


















                    • $begingroup$
                      I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
                      $endgroup$
                      – Mike Earnest
                      Dec 20 '18 at 18:15










                    • $begingroup$
                      I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
                      $endgroup$
                      – Julián Aguirre
                      Dec 20 '18 at 19:02
















                    $begingroup$
                    I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
                    $endgroup$
                    – Mike Earnest
                    Dec 20 '18 at 18:15




                    $begingroup$
                    I think you misread the definition of $star$ as $(astar b)_n=sum_k binom{n}k a_kb_k$, because your $T$ operator is unrelated to $sum_k binom{n}k a_k b_{n-k}$.
                    $endgroup$
                    – Mike Earnest
                    Dec 20 '18 at 18:15












                    $begingroup$
                    I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
                    $endgroup$
                    – Julián Aguirre
                    Dec 20 '18 at 19:02




                    $begingroup$
                    I see. I read $a_kb_k$ instead of $a_kb_{n-k}$.
                    $endgroup$
                    – Julián Aguirre
                    Dec 20 '18 at 19:02











                    1












                    $begingroup$

                    Given
                    $$
                    c_{,n} = ,sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k} a_{,k} ,b_{,n - k} }
                    $$

                    then notice that the e.g.f.'s are in the following relation
                    $$
                    eqalign{
                    & C(z) = sumlimits_{0, le ,n,} {{{c_{,n} } over {n!}},z^{,n} }
                    = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
                    a_{,k} ,b_{,n - k} ,z^{,n} } } = cr
                    & = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
                    a_{,k} z^{,k} ,b_{,n - k} z^{,n - k} ,} } = cr
                    & = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {{{a_{,k} } over {k!}}z^{,k}
                    ,{{b_{,n - k} } over {left( {n - k} right)!}}z^{,n - k} ,} } = cr
                    & = ,left( {sumlimits_{0, le ,n,} {{{a_{,k} } over {k!}}z^{,k} } } right)left( {sumlimits_{0, le ,j,} {,{{b_{,j} } over {j!}}z^{,j} ,} } right) = cr
                    & = ,A(z)B(z) cr}
                    $$



                    That premised, and passing for simplicity to the ordinary g.f.
                    $$
                    C(z) = sumlimits_{0, le ,n,} {c_{,n} ,z^{,n} }
                    = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {a_{,k} ,b_{,n - k} ,z^{,n} } } = A(z)B(z)
                    $$

                    if I understand properly your question and comment, you need to compute $D(z)$
                    $$
                    D(z) = sumlimits_{0, le ,n,} {a_{,n} b_{,n} ,z^{,n} }
                    $$

                    knowing $A(z)$ and $B(z)$ .



                    Then, assuming that these are convergent in a domain of non-null measure, you can use the
                    duality of the Convolution Theorem , same as for the Fourier series, which for the z-Transform
                    reads as
                    $$
                    D(z) = {1 over {i2pi }}ointlimits_C {A(z)B(z/v){{dv} over v}}
                    $$

                    refer to last entry of the table in this Wikipedia Article






                    share|cite|improve this answer











                    $endgroup$









                    • 1




                      $begingroup$
                      yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
                      $endgroup$
                      – Mohammad Al Jamal
                      Dec 20 '18 at 21:42












                    • $begingroup$
                      @MohammadAlJamal: added possible solution: don't know if I caught exactly your question
                      $endgroup$
                      – G Cab
                      Dec 21 '18 at 0:41






                    • 2




                      $begingroup$
                      $sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
                      $endgroup$
                      – reuns
                      Dec 21 '18 at 1:20


















                    1












                    $begingroup$

                    Given
                    $$
                    c_{,n} = ,sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k} a_{,k} ,b_{,n - k} }
                    $$

                    then notice that the e.g.f.'s are in the following relation
                    $$
                    eqalign{
                    & C(z) = sumlimits_{0, le ,n,} {{{c_{,n} } over {n!}},z^{,n} }
                    = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
                    a_{,k} ,b_{,n - k} ,z^{,n} } } = cr
                    & = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
                    a_{,k} z^{,k} ,b_{,n - k} z^{,n - k} ,} } = cr
                    & = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {{{a_{,k} } over {k!}}z^{,k}
                    ,{{b_{,n - k} } over {left( {n - k} right)!}}z^{,n - k} ,} } = cr
                    & = ,left( {sumlimits_{0, le ,n,} {{{a_{,k} } over {k!}}z^{,k} } } right)left( {sumlimits_{0, le ,j,} {,{{b_{,j} } over {j!}}z^{,j} ,} } right) = cr
                    & = ,A(z)B(z) cr}
                    $$



                    That premised, and passing for simplicity to the ordinary g.f.
                    $$
                    C(z) = sumlimits_{0, le ,n,} {c_{,n} ,z^{,n} }
                    = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {a_{,k} ,b_{,n - k} ,z^{,n} } } = A(z)B(z)
                    $$

                    if I understand properly your question and comment, you need to compute $D(z)$
                    $$
                    D(z) = sumlimits_{0, le ,n,} {a_{,n} b_{,n} ,z^{,n} }
                    $$

                    knowing $A(z)$ and $B(z)$ .



                    Then, assuming that these are convergent in a domain of non-null measure, you can use the
                    duality of the Convolution Theorem , same as for the Fourier series, which for the z-Transform
                    reads as
                    $$
                    D(z) = {1 over {i2pi }}ointlimits_C {A(z)B(z/v){{dv} over v}}
                    $$

                    refer to last entry of the table in this Wikipedia Article






                    share|cite|improve this answer











                    $endgroup$









                    • 1




                      $begingroup$
                      yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
                      $endgroup$
                      – Mohammad Al Jamal
                      Dec 20 '18 at 21:42












                    • $begingroup$
                      @MohammadAlJamal: added possible solution: don't know if I caught exactly your question
                      $endgroup$
                      – G Cab
                      Dec 21 '18 at 0:41






                    • 2




                      $begingroup$
                      $sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
                      $endgroup$
                      – reuns
                      Dec 21 '18 at 1:20
















                    1












                    1








                    1





                    $begingroup$

                    Given
                    $$
                    c_{,n} = ,sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k} a_{,k} ,b_{,n - k} }
                    $$

                    then notice that the e.g.f.'s are in the following relation
                    $$
                    eqalign{
                    & C(z) = sumlimits_{0, le ,n,} {{{c_{,n} } over {n!}},z^{,n} }
                    = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
                    a_{,k} ,b_{,n - k} ,z^{,n} } } = cr
                    & = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
                    a_{,k} z^{,k} ,b_{,n - k} z^{,n - k} ,} } = cr
                    & = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {{{a_{,k} } over {k!}}z^{,k}
                    ,{{b_{,n - k} } over {left( {n - k} right)!}}z^{,n - k} ,} } = cr
                    & = ,left( {sumlimits_{0, le ,n,} {{{a_{,k} } over {k!}}z^{,k} } } right)left( {sumlimits_{0, le ,j,} {,{{b_{,j} } over {j!}}z^{,j} ,} } right) = cr
                    & = ,A(z)B(z) cr}
                    $$



                    That premised, and passing for simplicity to the ordinary g.f.
                    $$
                    C(z) = sumlimits_{0, le ,n,} {c_{,n} ,z^{,n} }
                    = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {a_{,k} ,b_{,n - k} ,z^{,n} } } = A(z)B(z)
                    $$

                    if I understand properly your question and comment, you need to compute $D(z)$
                    $$
                    D(z) = sumlimits_{0, le ,n,} {a_{,n} b_{,n} ,z^{,n} }
                    $$

                    knowing $A(z)$ and $B(z)$ .



                    Then, assuming that these are convergent in a domain of non-null measure, you can use the
                    duality of the Convolution Theorem , same as for the Fourier series, which for the z-Transform
                    reads as
                    $$
                    D(z) = {1 over {i2pi }}ointlimits_C {A(z)B(z/v){{dv} over v}}
                    $$

                    refer to last entry of the table in this Wikipedia Article






                    share|cite|improve this answer











                    $endgroup$



                    Given
                    $$
                    c_{,n} = ,sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k} a_{,k} ,b_{,n - k} }
                    $$

                    then notice that the e.g.f.'s are in the following relation
                    $$
                    eqalign{
                    & C(z) = sumlimits_{0, le ,n,} {{{c_{,n} } over {n!}},z^{,n} }
                    = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
                    a_{,k} ,b_{,n - k} ,z^{,n} } } = cr
                    & = ,sumlimits_{0, le ,n,} {{1 over {n!}}sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {binom{n}{k}
                    a_{,k} z^{,k} ,b_{,n - k} z^{,n - k} ,} } = cr
                    & = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {{{a_{,k} } over {k!}}z^{,k}
                    ,{{b_{,n - k} } over {left( {n - k} right)!}}z^{,n - k} ,} } = cr
                    & = ,left( {sumlimits_{0, le ,n,} {{{a_{,k} } over {k!}}z^{,k} } } right)left( {sumlimits_{0, le ,j,} {,{{b_{,j} } over {j!}}z^{,j} ,} } right) = cr
                    & = ,A(z)B(z) cr}
                    $$



                    That premised, and passing for simplicity to the ordinary g.f.
                    $$
                    C(z) = sumlimits_{0, le ,n,} {c_{,n} ,z^{,n} }
                    = ,sumlimits_{0, le ,n,} {sumlimits_{left( {0, le } right),k,left( { le ,n} right)} {a_{,k} ,b_{,n - k} ,z^{,n} } } = A(z)B(z)
                    $$

                    if I understand properly your question and comment, you need to compute $D(z)$
                    $$
                    D(z) = sumlimits_{0, le ,n,} {a_{,n} b_{,n} ,z^{,n} }
                    $$

                    knowing $A(z)$ and $B(z)$ .



                    Then, assuming that these are convergent in a domain of non-null measure, you can use the
                    duality of the Convolution Theorem , same as for the Fourier series, which for the z-Transform
                    reads as
                    $$
                    D(z) = {1 over {i2pi }}ointlimits_C {A(z)B(z/v){{dv} over v}}
                    $$

                    refer to last entry of the table in this Wikipedia Article







                    share|cite|improve this answer














                    share|cite|improve this answer



                    share|cite|improve this answer








                    edited Dec 21 '18 at 0:39

























                    answered Dec 20 '18 at 20:01









                    G CabG Cab

                    19.5k31238




                    19.5k31238








                    • 1




                      $begingroup$
                      yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
                      $endgroup$
                      – Mohammad Al Jamal
                      Dec 20 '18 at 21:42












                    • $begingroup$
                      @MohammadAlJamal: added possible solution: don't know if I caught exactly your question
                      $endgroup$
                      – G Cab
                      Dec 21 '18 at 0:41






                    • 2




                      $begingroup$
                      $sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
                      $endgroup$
                      – reuns
                      Dec 21 '18 at 1:20
















                    • 1




                      $begingroup$
                      yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
                      $endgroup$
                      – Mohammad Al Jamal
                      Dec 20 '18 at 21:42












                    • $begingroup$
                      @MohammadAlJamal: added possible solution: don't know if I caught exactly your question
                      $endgroup$
                      – G Cab
                      Dec 21 '18 at 0:41






                    • 2




                      $begingroup$
                      $sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
                      $endgroup$
                      – reuns
                      Dec 21 '18 at 1:20










                    1




                    1




                    $begingroup$
                    yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
                    $endgroup$
                    – Mohammad Al Jamal
                    Dec 20 '18 at 21:42






                    $begingroup$
                    yes, i am aware of that. what i am seeking, though, is the Hadamard product of the OGFs of the two sequences, as opposed to the direct product of the EGFs. my question translates to : how to obtain the Hadamard product of the OGFs of the two sequences from $A(z)B(z)$ ?
                    $endgroup$
                    – Mohammad Al Jamal
                    Dec 20 '18 at 21:42














                    $begingroup$
                    @MohammadAlJamal: added possible solution: don't know if I caught exactly your question
                    $endgroup$
                    – G Cab
                    Dec 21 '18 at 0:41




                    $begingroup$
                    @MohammadAlJamal: added possible solution: don't know if I caught exactly your question
                    $endgroup$
                    – G Cab
                    Dec 21 '18 at 0:41




                    2




                    2




                    $begingroup$
                    $sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
                    $endgroup$
                    – reuns
                    Dec 21 '18 at 1:20






                    $begingroup$
                    $sum_{k=0}^n {n choose k} a_k b_{n-k} = frac{1}{n!} (A ast B)(n)$ where $ast$ is the usual convolution and $A_n = a_n n! ,B_n = b_n n!$. So in general you can't recover $A B$ only from $A ast B$ as if $u ast v = 1_{n=0}$ then replacing $A,B$ by $A ast u, B ast v$ doesn't change $A ast B$ but changes $AB$ @MohammadAlJamal
                    $endgroup$
                    – reuns
                    Dec 21 '18 at 1:20




















                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Mathematics Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047527%2finverting-the-binomial-convolution-of-sequences%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Quarter-circle Tiles

                    build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

                    Mont Emei