Solve the recurrence relation $a_n=a_{n-1}+2n+3a_{n-3}?$












0












$begingroup$


I am currently solving a recurrence relation but I got stuck since I am not even able to find the basic root of the auxiliary equations.










share|cite|improve this question











$endgroup$












  • $begingroup$
    Do you mean $a_n = a_{n-1} + 2n + 3a_{n-3}$ or $a_n = a_{n-2} + 2 a_{n-2} + 3 a_{n-3}$ (or something else entirely)?
    $endgroup$
    – Connor Harris
    Jan 17 at 14:41










  • $begingroup$
    First one!!!!!!
    $endgroup$
    – Sagar Sharma
    Jan 17 at 14:43










  • $begingroup$
    Do you have initial conditions?
    $endgroup$
    – Adrian Keister
    Jan 17 at 14:49










  • $begingroup$
    Initial conditions are varying.
    $endgroup$
    – Sagar Sharma
    Jan 17 at 14:51








  • 1




    $begingroup$
    Let $a_n=b_n+p+qn$ to eliminate $n$
    $endgroup$
    – lab bhattacharjee
    Jan 17 at 15:16
















0












$begingroup$


I am currently solving a recurrence relation but I got stuck since I am not even able to find the basic root of the auxiliary equations.










share|cite|improve this question











$endgroup$












  • $begingroup$
    Do you mean $a_n = a_{n-1} + 2n + 3a_{n-3}$ or $a_n = a_{n-2} + 2 a_{n-2} + 3 a_{n-3}$ (or something else entirely)?
    $endgroup$
    – Connor Harris
    Jan 17 at 14:41










  • $begingroup$
    First one!!!!!!
    $endgroup$
    – Sagar Sharma
    Jan 17 at 14:43










  • $begingroup$
    Do you have initial conditions?
    $endgroup$
    – Adrian Keister
    Jan 17 at 14:49










  • $begingroup$
    Initial conditions are varying.
    $endgroup$
    – Sagar Sharma
    Jan 17 at 14:51








  • 1




    $begingroup$
    Let $a_n=b_n+p+qn$ to eliminate $n$
    $endgroup$
    – lab bhattacharjee
    Jan 17 at 15:16














0












0








0


1



$begingroup$


I am currently solving a recurrence relation but I got stuck since I am not even able to find the basic root of the auxiliary equations.










share|cite|improve this question











$endgroup$




I am currently solving a recurrence relation but I got stuck since I am not even able to find the basic root of the auxiliary equations.







recurrence-relations homogeneous-equation






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 17 at 14:48









Adrian Keister

5,26571933




5,26571933










asked Jan 17 at 14:36









Sagar SharmaSagar Sharma

143




143












  • $begingroup$
    Do you mean $a_n = a_{n-1} + 2n + 3a_{n-3}$ or $a_n = a_{n-2} + 2 a_{n-2} + 3 a_{n-3}$ (or something else entirely)?
    $endgroup$
    – Connor Harris
    Jan 17 at 14:41










  • $begingroup$
    First one!!!!!!
    $endgroup$
    – Sagar Sharma
    Jan 17 at 14:43










  • $begingroup$
    Do you have initial conditions?
    $endgroup$
    – Adrian Keister
    Jan 17 at 14:49










  • $begingroup$
    Initial conditions are varying.
    $endgroup$
    – Sagar Sharma
    Jan 17 at 14:51








  • 1




    $begingroup$
    Let $a_n=b_n+p+qn$ to eliminate $n$
    $endgroup$
    – lab bhattacharjee
    Jan 17 at 15:16


















  • $begingroup$
    Do you mean $a_n = a_{n-1} + 2n + 3a_{n-3}$ or $a_n = a_{n-2} + 2 a_{n-2} + 3 a_{n-3}$ (or something else entirely)?
    $endgroup$
    – Connor Harris
    Jan 17 at 14:41










  • $begingroup$
    First one!!!!!!
    $endgroup$
    – Sagar Sharma
    Jan 17 at 14:43










  • $begingroup$
    Do you have initial conditions?
    $endgroup$
    – Adrian Keister
    Jan 17 at 14:49










  • $begingroup$
    Initial conditions are varying.
    $endgroup$
    – Sagar Sharma
    Jan 17 at 14:51








  • 1




    $begingroup$
    Let $a_n=b_n+p+qn$ to eliminate $n$
    $endgroup$
    – lab bhattacharjee
    Jan 17 at 15:16
















$begingroup$
Do you mean $a_n = a_{n-1} + 2n + 3a_{n-3}$ or $a_n = a_{n-2} + 2 a_{n-2} + 3 a_{n-3}$ (or something else entirely)?
$endgroup$
– Connor Harris
Jan 17 at 14:41




$begingroup$
Do you mean $a_n = a_{n-1} + 2n + 3a_{n-3}$ or $a_n = a_{n-2} + 2 a_{n-2} + 3 a_{n-3}$ (or something else entirely)?
$endgroup$
– Connor Harris
Jan 17 at 14:41












$begingroup$
First one!!!!!!
$endgroup$
– Sagar Sharma
Jan 17 at 14:43




$begingroup$
First one!!!!!!
$endgroup$
– Sagar Sharma
Jan 17 at 14:43












$begingroup$
Do you have initial conditions?
$endgroup$
– Adrian Keister
Jan 17 at 14:49




$begingroup$
Do you have initial conditions?
$endgroup$
– Adrian Keister
Jan 17 at 14:49












$begingroup$
Initial conditions are varying.
$endgroup$
– Sagar Sharma
Jan 17 at 14:51






$begingroup$
Initial conditions are varying.
$endgroup$
– Sagar Sharma
Jan 17 at 14:51






1




1




$begingroup$
Let $a_n=b_n+p+qn$ to eliminate $n$
$endgroup$
– lab bhattacharjee
Jan 17 at 15:16




$begingroup$
Let $a_n=b_n+p+qn$ to eliminate $n$
$endgroup$
– lab bhattacharjee
Jan 17 at 15:16










1 Answer
1






active

oldest

votes


















1












$begingroup$

Let's rewrite this as
begin{align*}
a_{n+3} = a_{n+2} + 2(n+3) + 3a_n
end{align*}

The generating function for this sequence is
begin{align*}
frac{f(x) - a_0 - a_1x - a_2x^2}{x^3} = frac{f(x) - a_0 - a_1x}{x^2} + frac{2(3 - 2x)}{(1-x)^2} + 3f(x)
end{align*}

Solving for $f(x)$ gives us
begin{align*}
f(x) = color{blue}{frac{a_0(x-1)}{(3x^3+x-1)}} + color{red}{frac{a_1 x(x-1)}{(3x^3+x-1)}} - color{green}{frac{a_2x^2}{(3x^3+x-1)}} - color{orange}{frac{2(3-2x)x^3}{(x-1)^2(3x^3+x-1)}}
end{align*}

Let $r_1, r_2, r_3$ be the roots of $3x^3 + x - 1=0$. Then the series expansion of the blue term is
begin{align*}
sum_{n=0}^{infty}underbrace{left{frac{a_0}{3}left(frac{1 - r_1}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{1 - r_2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{1 - r_3}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{p_n}x^n
end{align*}

Similarly, the red portion is
begin{align*}
sum_{n=0}^{infty}underbrace{left{frac{a_1}{3}left(frac{r_1(1 - r_1)}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{r_2(1 - r_2)}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{r_3(1 - r_3)}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{q_n}x^n
end{align*}

The green portion is
begin{align*}
sum_{n=0}^{infty}underbrace{left{frac{a_2}{3}left(frac{r_1^2}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{r_2^2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{r_3^2}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{r_n}x^n
end{align*}

Exercise Find the series expansion for the orange term, and call the coefficients as $s_n$.



Finally, your sequence can be expressed as
begin{align*}
a_n = p_n + q_n - r_n - s_n
end{align*}

There is some heavy simplification you can do. For example, you can express
begin{align*}
p_n + q_n - r_n=sum_{t=1}^{3}frac{1}{r_t^{n+1}}g_t(a_0, a_1, a_2, r_1, r_2, r_3)
end{align*}

For functions $g_1, g_2, g_3$, which you can pre-compute in a computer implementation.






share|cite|improve this answer











$endgroup$













    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%2f3077056%2fsolve-the-recurrence-relation-a-n-a-n-12n3a-n-3%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    1












    $begingroup$

    Let's rewrite this as
    begin{align*}
    a_{n+3} = a_{n+2} + 2(n+3) + 3a_n
    end{align*}

    The generating function for this sequence is
    begin{align*}
    frac{f(x) - a_0 - a_1x - a_2x^2}{x^3} = frac{f(x) - a_0 - a_1x}{x^2} + frac{2(3 - 2x)}{(1-x)^2} + 3f(x)
    end{align*}

    Solving for $f(x)$ gives us
    begin{align*}
    f(x) = color{blue}{frac{a_0(x-1)}{(3x^3+x-1)}} + color{red}{frac{a_1 x(x-1)}{(3x^3+x-1)}} - color{green}{frac{a_2x^2}{(3x^3+x-1)}} - color{orange}{frac{2(3-2x)x^3}{(x-1)^2(3x^3+x-1)}}
    end{align*}

    Let $r_1, r_2, r_3$ be the roots of $3x^3 + x - 1=0$. Then the series expansion of the blue term is
    begin{align*}
    sum_{n=0}^{infty}underbrace{left{frac{a_0}{3}left(frac{1 - r_1}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{1 - r_2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{1 - r_3}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{p_n}x^n
    end{align*}

    Similarly, the red portion is
    begin{align*}
    sum_{n=0}^{infty}underbrace{left{frac{a_1}{3}left(frac{r_1(1 - r_1)}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{r_2(1 - r_2)}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{r_3(1 - r_3)}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{q_n}x^n
    end{align*}

    The green portion is
    begin{align*}
    sum_{n=0}^{infty}underbrace{left{frac{a_2}{3}left(frac{r_1^2}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{r_2^2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{r_3^2}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{r_n}x^n
    end{align*}

    Exercise Find the series expansion for the orange term, and call the coefficients as $s_n$.



    Finally, your sequence can be expressed as
    begin{align*}
    a_n = p_n + q_n - r_n - s_n
    end{align*}

    There is some heavy simplification you can do. For example, you can express
    begin{align*}
    p_n + q_n - r_n=sum_{t=1}^{3}frac{1}{r_t^{n+1}}g_t(a_0, a_1, a_2, r_1, r_2, r_3)
    end{align*}

    For functions $g_1, g_2, g_3$, which you can pre-compute in a computer implementation.






    share|cite|improve this answer











    $endgroup$


















      1












      $begingroup$

      Let's rewrite this as
      begin{align*}
      a_{n+3} = a_{n+2} + 2(n+3) + 3a_n
      end{align*}

      The generating function for this sequence is
      begin{align*}
      frac{f(x) - a_0 - a_1x - a_2x^2}{x^3} = frac{f(x) - a_0 - a_1x}{x^2} + frac{2(3 - 2x)}{(1-x)^2} + 3f(x)
      end{align*}

      Solving for $f(x)$ gives us
      begin{align*}
      f(x) = color{blue}{frac{a_0(x-1)}{(3x^3+x-1)}} + color{red}{frac{a_1 x(x-1)}{(3x^3+x-1)}} - color{green}{frac{a_2x^2}{(3x^3+x-1)}} - color{orange}{frac{2(3-2x)x^3}{(x-1)^2(3x^3+x-1)}}
      end{align*}

      Let $r_1, r_2, r_3$ be the roots of $3x^3 + x - 1=0$. Then the series expansion of the blue term is
      begin{align*}
      sum_{n=0}^{infty}underbrace{left{frac{a_0}{3}left(frac{1 - r_1}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{1 - r_2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{1 - r_3}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{p_n}x^n
      end{align*}

      Similarly, the red portion is
      begin{align*}
      sum_{n=0}^{infty}underbrace{left{frac{a_1}{3}left(frac{r_1(1 - r_1)}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{r_2(1 - r_2)}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{r_3(1 - r_3)}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{q_n}x^n
      end{align*}

      The green portion is
      begin{align*}
      sum_{n=0}^{infty}underbrace{left{frac{a_2}{3}left(frac{r_1^2}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{r_2^2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{r_3^2}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{r_n}x^n
      end{align*}

      Exercise Find the series expansion for the orange term, and call the coefficients as $s_n$.



      Finally, your sequence can be expressed as
      begin{align*}
      a_n = p_n + q_n - r_n - s_n
      end{align*}

      There is some heavy simplification you can do. For example, you can express
      begin{align*}
      p_n + q_n - r_n=sum_{t=1}^{3}frac{1}{r_t^{n+1}}g_t(a_0, a_1, a_2, r_1, r_2, r_3)
      end{align*}

      For functions $g_1, g_2, g_3$, which you can pre-compute in a computer implementation.






      share|cite|improve this answer











      $endgroup$
















        1












        1








        1





        $begingroup$

        Let's rewrite this as
        begin{align*}
        a_{n+3} = a_{n+2} + 2(n+3) + 3a_n
        end{align*}

        The generating function for this sequence is
        begin{align*}
        frac{f(x) - a_0 - a_1x - a_2x^2}{x^3} = frac{f(x) - a_0 - a_1x}{x^2} + frac{2(3 - 2x)}{(1-x)^2} + 3f(x)
        end{align*}

        Solving for $f(x)$ gives us
        begin{align*}
        f(x) = color{blue}{frac{a_0(x-1)}{(3x^3+x-1)}} + color{red}{frac{a_1 x(x-1)}{(3x^3+x-1)}} - color{green}{frac{a_2x^2}{(3x^3+x-1)}} - color{orange}{frac{2(3-2x)x^3}{(x-1)^2(3x^3+x-1)}}
        end{align*}

        Let $r_1, r_2, r_3$ be the roots of $3x^3 + x - 1=0$. Then the series expansion of the blue term is
        begin{align*}
        sum_{n=0}^{infty}underbrace{left{frac{a_0}{3}left(frac{1 - r_1}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{1 - r_2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{1 - r_3}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{p_n}x^n
        end{align*}

        Similarly, the red portion is
        begin{align*}
        sum_{n=0}^{infty}underbrace{left{frac{a_1}{3}left(frac{r_1(1 - r_1)}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{r_2(1 - r_2)}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{r_3(1 - r_3)}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{q_n}x^n
        end{align*}

        The green portion is
        begin{align*}
        sum_{n=0}^{infty}underbrace{left{frac{a_2}{3}left(frac{r_1^2}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{r_2^2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{r_3^2}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{r_n}x^n
        end{align*}

        Exercise Find the series expansion for the orange term, and call the coefficients as $s_n$.



        Finally, your sequence can be expressed as
        begin{align*}
        a_n = p_n + q_n - r_n - s_n
        end{align*}

        There is some heavy simplification you can do. For example, you can express
        begin{align*}
        p_n + q_n - r_n=sum_{t=1}^{3}frac{1}{r_t^{n+1}}g_t(a_0, a_1, a_2, r_1, r_2, r_3)
        end{align*}

        For functions $g_1, g_2, g_3$, which you can pre-compute in a computer implementation.






        share|cite|improve this answer











        $endgroup$



        Let's rewrite this as
        begin{align*}
        a_{n+3} = a_{n+2} + 2(n+3) + 3a_n
        end{align*}

        The generating function for this sequence is
        begin{align*}
        frac{f(x) - a_0 - a_1x - a_2x^2}{x^3} = frac{f(x) - a_0 - a_1x}{x^2} + frac{2(3 - 2x)}{(1-x)^2} + 3f(x)
        end{align*}

        Solving for $f(x)$ gives us
        begin{align*}
        f(x) = color{blue}{frac{a_0(x-1)}{(3x^3+x-1)}} + color{red}{frac{a_1 x(x-1)}{(3x^3+x-1)}} - color{green}{frac{a_2x^2}{(3x^3+x-1)}} - color{orange}{frac{2(3-2x)x^3}{(x-1)^2(3x^3+x-1)}}
        end{align*}

        Let $r_1, r_2, r_3$ be the roots of $3x^3 + x - 1=0$. Then the series expansion of the blue term is
        begin{align*}
        sum_{n=0}^{infty}underbrace{left{frac{a_0}{3}left(frac{1 - r_1}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{1 - r_2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{1 - r_3}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{p_n}x^n
        end{align*}

        Similarly, the red portion is
        begin{align*}
        sum_{n=0}^{infty}underbrace{left{frac{a_1}{3}left(frac{r_1(1 - r_1)}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{r_2(1 - r_2)}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{r_3(1 - r_3)}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{q_n}x^n
        end{align*}

        The green portion is
        begin{align*}
        sum_{n=0}^{infty}underbrace{left{frac{a_2}{3}left(frac{r_1^2}{r_1^{n+1}(r_1 - r_2)(r_1 - r_3)} + frac{r_2^2}{r_2^{n+1}(r_2 - r_1)(r_2 - r_3)} + frac{r_3^2}{r_3^{n+1}(r_3 - r_1)(r_3 - r_2)}right)right}}_{r_n}x^n
        end{align*}

        Exercise Find the series expansion for the orange term, and call the coefficients as $s_n$.



        Finally, your sequence can be expressed as
        begin{align*}
        a_n = p_n + q_n - r_n - s_n
        end{align*}

        There is some heavy simplification you can do. For example, you can express
        begin{align*}
        p_n + q_n - r_n=sum_{t=1}^{3}frac{1}{r_t^{n+1}}g_t(a_0, a_1, a_2, r_1, r_2, r_3)
        end{align*}

        For functions $g_1, g_2, g_3$, which you can pre-compute in a computer implementation.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Jan 17 at 16:38

























        answered Jan 17 at 16:30









        Tom ChenTom Chen

        1,568715




        1,568715






























            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%2f3077056%2fsolve-the-recurrence-relation-a-n-a-n-12n3a-n-3%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

            Can a sorcerer learn a 5th-level spell early by creating spell slots using the Font of Magic feature?

            Does disintegrating a polymorphed enemy still kill it after the 2018 errata?

            A Topological Invariant for $pi_3(U(n))$