Recursion and Catalan Numbers

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
2
down vote

favorite













Consider the sequence defined by
$$
begincases
r_0=1\
r_1=3\
r_n=6r_n-1-9r_n-2 & textif nge 2
endcases
.$$
Find a closed form for $r_n$.



Your response should be a formula in terms of $n$, and should not contain terms such as $r_n,$ $r_n-1,$ and so on. Do not include $``r_n=text''$ in your response.




I realize that the characteristic equation of the recurrence is $c^2-6c+9$ and that can be factored into $(c-3)(c-3)$. So, I then have $$r_0 = lambda_1+lambda_2$$ and $$r_1 = 3lambda_1+3lambda_2.$$ But shouldn't this have infinite solutions?




catalan-numbers




share|cite|improve this question
























    up vote
    2
    down vote

    favorite













    Consider the sequence defined by
    $$
    begincases
    r_0=1\
    r_1=3\
    r_n=6r_n-1-9r_n-2 & textif nge 2
    endcases
    .$$
    Find a closed form for $r_n$.



    Your response should be a formula in terms of $n$, and should not contain terms such as $r_n,$ $r_n-1,$ and so on. Do not include $``r_n=text''$ in your response.




    I realize that the characteristic equation of the recurrence is $c^2-6c+9$ and that can be factored into $(c-3)(c-3)$. So, I then have $$r_0 = lambda_1+lambda_2$$ and $$r_1 = 3lambda_1+3lambda_2.$$ But shouldn't this have infinite solutions?




    catalan-numbers




    share|cite|improve this question






















      up vote
      2
      down vote

      favorite









      up vote
      2
      down vote

      favorite












      Consider the sequence defined by
      $$
      begincases
      r_0=1\
      r_1=3\
      r_n=6r_n-1-9r_n-2 & textif nge 2
      endcases
      .$$
      Find a closed form for $r_n$.



      Your response should be a formula in terms of $n$, and should not contain terms such as $r_n,$ $r_n-1,$ and so on. Do not include $``r_n=text''$ in your response.




      I realize that the characteristic equation of the recurrence is $c^2-6c+9$ and that can be factored into $(c-3)(c-3)$. So, I then have $$r_0 = lambda_1+lambda_2$$ and $$r_1 = 3lambda_1+3lambda_2.$$ But shouldn't this have infinite solutions?




      catalan-numbers




      share|cite|improve this question













      Consider the sequence defined by
      $$
      begincases
      r_0=1\
      r_1=3\
      r_n=6r_n-1-9r_n-2 & textif nge 2
      endcases
      .$$
      Find a closed form for $r_n$.



      Your response should be a formula in terms of $n$, and should not contain terms such as $r_n,$ $r_n-1,$ and so on. Do not include $``r_n=text''$ in your response.




      I realize that the characteristic equation of the recurrence is $c^2-6c+9$ and that can be factored into $(c-3)(c-3)$. So, I then have $$r_0 = lambda_1+lambda_2$$ and $$r_1 = 3lambda_1+3lambda_2.$$ But shouldn't this have infinite solutions?





      catalan-numbers





      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Aug 25 at 5:35









      WolverineA03

      1427




      1427




















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          1
          down vote













          Hint. This is a constant-recursive sequence in which the characteristic polynomial has a double root equal to $3$. In this case, the general term has the form $c_n = (lambda_1 + n lambda_2)3^n$.






          share|cite|improve this answer




















            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',
            convertImagesToLinks: true,
            noModals: false,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            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%2f2893819%2frecursion-and-catalan-numbers%23new-answer', 'question_page');

            );

            Post as a guest

















            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            1
            down vote













            Hint. This is a constant-recursive sequence in which the characteristic polynomial has a double root equal to $3$. In this case, the general term has the form $c_n = (lambda_1 + n lambda_2)3^n$.






            share|cite|improve this answer
























              up vote
              1
              down vote













              Hint. This is a constant-recursive sequence in which the characteristic polynomial has a double root equal to $3$. In this case, the general term has the form $c_n = (lambda_1 + n lambda_2)3^n$.






              share|cite|improve this answer






















                up vote
                1
                down vote










                up vote
                1
                down vote









                Hint. This is a constant-recursive sequence in which the characteristic polynomial has a double root equal to $3$. In this case, the general term has the form $c_n = (lambda_1 + n lambda_2)3^n$.






                share|cite|improve this answer












                Hint. This is a constant-recursive sequence in which the characteristic polynomial has a double root equal to $3$. In this case, the general term has the form $c_n = (lambda_1 + n lambda_2)3^n$.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Aug 25 at 6:11









                J.-E. Pin

                17.5k21753




                17.5k21753



























                     

                    draft saved


                    draft discarded















































                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2893819%2frecursion-and-catalan-numbers%23new-answer', 'question_page');

                    );

                    Post as a guest
































































                    -

                    這個網誌中的熱門文章

                    Is there any way to eliminate the singular point to solve this integral by hand or by approximations?

                    圖片
                    Clash Royale CLAN TAG #URR8PPP up vote 0 down vote favorite 1 $$int_0^1 (1+(x^-p-1)^1-p)^frac1pdx, pin mathbbR, pge 1$$ I find that $x=0,1$ are singular points(discontinuous points of this integral), is there a way to eliminate those singular points to make sure that this integral can be calculated by hand or by Taylor approximations. In either cases, what are those steps of calculating the integral? calculus real-analysis analysis approximation share | cite | improve this question edited Sep 11 at 5:07 asked Sep 11 at 4:48 Mclalalala 126 8 1 What is $p$? Please give more information to make it complete. – xbh Sep 11 at 5:02 @xbh already fixed it, thanks for reminding. – Mclalalala Sep 11 at 5:10 Seems that $0$ is not singular here… [I might compute wrong] – xbh Sep 11 at 5:30 @xbh can you show me how to get the close formula for the integral above? – Mclalalala Sep 11 at 5:33
                    閱讀完整內容

                    Why am i infinitely getting the same tweet with the Twitter Search API?

                    圖片
                    up vote 0 down vote favorite My code workes perfectly for other queries, but for one query I am infinitely getting the same tweet. I can't understand what the problem is. API call: query='Allergic asthma OR Nonallergic asthma OR Occupational asthma OR EIB OR Exercise-induced bronchoconstriction OR Nocturnal asthma OR Cough-variant asthma' new_tweets = api.search(q=searchQuery, count=100, since_id=since_id, lang='en',tweet_mode='extended') if not new_tweets: print("No more tweets found") break for tweet in new_tweets: if True: print(jsonpickle.encode(tweet._json, unpicklable=False)) my_file = open('searchTweets.txt','a') my_file.write(jsonpickle.encode(tweet._json, unpicklable=False)+'n') my_file.close() else: continue Output in file: https://pastebin.com/JmRCsTeE These are the JSONs of the same Tweet. Other queries that work: Breast cancer OR Prostate cancer OR Colon cancer OR Lung cancer Type 2 dia
                    閱讀完整內容

                    Carbon dioxide

                    圖片
                    "CO2" redirects here. For other uses, see CO2 (disambiguation). Carbon dioxide Names Other names Carbonic acid gas Carbonic anhydride Carbonic oxide Carbon oxide Carbon(IV) oxide Dry ice (solid phase) Identifiers CAS Number 124-38-9   Y 3D model (JSmol) Interactive image Interactive image 3DMet B01131 Beilstein Reference 1900390 ChEBI CHEBI:16526   Y ChEMBL ChEMBL1231871   N ChemSpider 274   Y ECHA InfoCard 100.004.271 EC Number 204-696-9 E number E290 (preservatives) Gmelin Reference 989 KEGG D00004   Y MeSH Carbon+dioxide PubChem CID 280 RTECS number FF6400000 UNII 142M471B3J   Y UN number 1013 (gas), 1845 (solid) InChI InChI=1S/CO2/c2-1-3   Y Key: CURLTUGMZLYLDI-UHFFFAOYSA-N   Y InChI=1/CO2/c2-1-3 Key: CURLTUGMZLYLDI-UHFFFAOYAO SMILES O=C=O C(=O)=O Properties Chemical formula C O 2 Molar mass 44.01 g·mol −1 Appearance Colorless gas Odor Low concentrations: none High concentrations: sharp; acidic [1] Density 1562 kg/m 3 (solid at 1 atm and −78.5 °C) 1101 kg/m 3 (liquid at
                    閱讀完整內容