Solving a recurrence relation (poker chips)What is the recurrence relation in this problem?How many ways can...

Which is the best way to check return result?

I would say: "You are another teacher", but she is a woman and I am a man

When is человек used as the word man instead of человек

How dangerous is XSS?

Why didn't Miles's spider sense work before?

Is it logically or scientifically possible to artificially send energy to the body?

What exploit Are these user agents trying to use?

Why is consensus so controversial in Britain?

What's the in-universe reasoning behind sorcerers needing material components?

Alternative to sending password over mail?

How do I gain back my faith in my PhD degree?

What killed these X2 caps?

What are some good books on Machine Learning and AI like Krugman, Wells and Graddy's "Essentials of Economics"

How can saying a song's name be a copyright violation?

If human space travel is limited by the G force vulnerability, is there a way to counter G forces?

Why didn't Boeing produce its own regional jet?

Forgetting the musical notes while performing in concert

Size of subfigure fitting its content (tikzpicture)

Assassin's bullet with mercury

iPad being using in wall mount battery swollen

How to prevent "they're falling in love" trope

How much of data wrangling is a data scientist's job?

In 'Revenger,' what does 'cove' come from?

Can a virus destroy the BIOS of a modern computer?



Solving a recurrence relation (poker chips)


What is the recurrence relation in this problem?How many ways can we divide line segment of length n into length 2 and 3 segmentsRecurrence relation word problemSolving a recurrence relation directlyRecurrence Relation for Stacking ChipsCombinations of a Bracelet?Number of ways to stack poker chips if two stacks that can be obtained from each other by reflection are considered to be equivalent?Problem with poker chipsrecurrence relation for the number of ways to make a pile of $n$ poker chips using red, white, and blue chipsnumber of ways to make a pile of $n$ poker chips using red, white, and blue chips and such that no two red chips are together













2












$begingroup$


Suppose that you have a large supply of red, white, green, and blue poker chips. You want to
make a vertical stack of n chips in such a way that the stack does not contain any consecutive
blue chips.



I've already found the recurrence relation for $a_{n}$ (where an denotes the number of ways you can make
such a stack of n poker chips):
$a_{n}=3a_{n-1}+3a_{n-2}$



But I am unsure of how to go about solving it. After solving it, I'm supposed to consider the specific case where you want to count only the stacks that use exactly 10 chips, and count $a_{10}$ directly.



Any help in the right direction is greatly appreciated!










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    For the recurrence relation you have not given the initial values of $a_0$ and $a_1$
    $endgroup$
    – Martin Hansen
    3 hours ago








  • 1




    $begingroup$
    I don't think the recurrence relation is correct. Happy to be told it is; has anyone else checked it ?
    $endgroup$
    – Martin Hansen
    2 hours ago






  • 1




    $begingroup$
    @MartinHansen A quick check shows that the sequence starts with $1$, $4$, $15$, $57$, which indeed does not satisfy the recurrence.
    $endgroup$
    – Servaes
    2 hours ago










  • $begingroup$
    @Servaes Thanks for the confirmation : I've now added an answer based on the correct recurrence relation
    $endgroup$
    – Martin Hansen
    1 hour ago
















2












$begingroup$


Suppose that you have a large supply of red, white, green, and blue poker chips. You want to
make a vertical stack of n chips in such a way that the stack does not contain any consecutive
blue chips.



I've already found the recurrence relation for $a_{n}$ (where an denotes the number of ways you can make
such a stack of n poker chips):
$a_{n}=3a_{n-1}+3a_{n-2}$



But I am unsure of how to go about solving it. After solving it, I'm supposed to consider the specific case where you want to count only the stacks that use exactly 10 chips, and count $a_{10}$ directly.



Any help in the right direction is greatly appreciated!










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    For the recurrence relation you have not given the initial values of $a_0$ and $a_1$
    $endgroup$
    – Martin Hansen
    3 hours ago








  • 1




    $begingroup$
    I don't think the recurrence relation is correct. Happy to be told it is; has anyone else checked it ?
    $endgroup$
    – Martin Hansen
    2 hours ago






  • 1




    $begingroup$
    @MartinHansen A quick check shows that the sequence starts with $1$, $4$, $15$, $57$, which indeed does not satisfy the recurrence.
    $endgroup$
    – Servaes
    2 hours ago










  • $begingroup$
    @Servaes Thanks for the confirmation : I've now added an answer based on the correct recurrence relation
    $endgroup$
    – Martin Hansen
    1 hour ago














2












2








2





$begingroup$


Suppose that you have a large supply of red, white, green, and blue poker chips. You want to
make a vertical stack of n chips in such a way that the stack does not contain any consecutive
blue chips.



I've already found the recurrence relation for $a_{n}$ (where an denotes the number of ways you can make
such a stack of n poker chips):
$a_{n}=3a_{n-1}+3a_{n-2}$



But I am unsure of how to go about solving it. After solving it, I'm supposed to consider the specific case where you want to count only the stacks that use exactly 10 chips, and count $a_{10}$ directly.



Any help in the right direction is greatly appreciated!










share|cite|improve this question











$endgroup$




Suppose that you have a large supply of red, white, green, and blue poker chips. You want to
make a vertical stack of n chips in such a way that the stack does not contain any consecutive
blue chips.



I've already found the recurrence relation for $a_{n}$ (where an denotes the number of ways you can make
such a stack of n poker chips):
$a_{n}=3a_{n-1}+3a_{n-2}$



But I am unsure of how to go about solving it. After solving it, I'm supposed to consider the specific case where you want to count only the stacks that use exactly 10 chips, and count $a_{10}$ directly.



Any help in the right direction is greatly appreciated!







combinatorics recurrence-relations






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 52 mins ago







Esther Rose

















asked 3 hours ago









Esther RoseEsther Rose

675




675








  • 1




    $begingroup$
    For the recurrence relation you have not given the initial values of $a_0$ and $a_1$
    $endgroup$
    – Martin Hansen
    3 hours ago








  • 1




    $begingroup$
    I don't think the recurrence relation is correct. Happy to be told it is; has anyone else checked it ?
    $endgroup$
    – Martin Hansen
    2 hours ago






  • 1




    $begingroup$
    @MartinHansen A quick check shows that the sequence starts with $1$, $4$, $15$, $57$, which indeed does not satisfy the recurrence.
    $endgroup$
    – Servaes
    2 hours ago










  • $begingroup$
    @Servaes Thanks for the confirmation : I've now added an answer based on the correct recurrence relation
    $endgroup$
    – Martin Hansen
    1 hour ago














  • 1




    $begingroup$
    For the recurrence relation you have not given the initial values of $a_0$ and $a_1$
    $endgroup$
    – Martin Hansen
    3 hours ago








  • 1




    $begingroup$
    I don't think the recurrence relation is correct. Happy to be told it is; has anyone else checked it ?
    $endgroup$
    – Martin Hansen
    2 hours ago






  • 1




    $begingroup$
    @MartinHansen A quick check shows that the sequence starts with $1$, $4$, $15$, $57$, which indeed does not satisfy the recurrence.
    $endgroup$
    – Servaes
    2 hours ago










  • $begingroup$
    @Servaes Thanks for the confirmation : I've now added an answer based on the correct recurrence relation
    $endgroup$
    – Martin Hansen
    1 hour ago








1




1




$begingroup$
For the recurrence relation you have not given the initial values of $a_0$ and $a_1$
$endgroup$
– Martin Hansen
3 hours ago






$begingroup$
For the recurrence relation you have not given the initial values of $a_0$ and $a_1$
$endgroup$
– Martin Hansen
3 hours ago






1




1




$begingroup$
I don't think the recurrence relation is correct. Happy to be told it is; has anyone else checked it ?
$endgroup$
– Martin Hansen
2 hours ago




$begingroup$
I don't think the recurrence relation is correct. Happy to be told it is; has anyone else checked it ?
$endgroup$
– Martin Hansen
2 hours ago




1




1




$begingroup$
@MartinHansen A quick check shows that the sequence starts with $1$, $4$, $15$, $57$, which indeed does not satisfy the recurrence.
$endgroup$
– Servaes
2 hours ago




$begingroup$
@MartinHansen A quick check shows that the sequence starts with $1$, $4$, $15$, $57$, which indeed does not satisfy the recurrence.
$endgroup$
– Servaes
2 hours ago












$begingroup$
@Servaes Thanks for the confirmation : I've now added an answer based on the correct recurrence relation
$endgroup$
– Martin Hansen
1 hour ago




$begingroup$
@Servaes Thanks for the confirmation : I've now added an answer based on the correct recurrence relation
$endgroup$
– Martin Hansen
1 hour ago










4 Answers
4






active

oldest

votes


















1












$begingroup$

Thanks for an interesting question.



The recurrence relation given in the question is not correct, albeit with only a sign error.



It should be;
$$a_n=3a_{n-1}+3a_{n-2}$$
$$a_0=1 : a_1=4$$
This gives rise to the generating series,
$$1+4x+15x^2+57x^3+216x^4+819x^5+dots+169209x^9+641520x^{10}+2432187x^{11}+dots$$
So, assuming the initial term is $a_0$, $a_{10}=641520$, which you asked for.



This generating series has generating function,
$$frac{1+x}{1-3x-3x^2}$$
Applying partial fractions to this gives, after some algebra,
$$frac{1+x}{1-3x-3x^2}=frac{21-5 sqrt{21}}{42 big( 1-frac{3-sqrt{21}}{2}x big)}+frac{21+5 sqrt{21}}{42 big( 1-frac{3+sqrt{21}}{2}x big)}$$
which are recognisable as standard bits directly translating into a formula for the $n^{th}$ term,
$$T_n=left( frac{1}{2}-frac{5 sqrt {21}}{42} right)left( frac{3 - sqrt {21}}{2} right)^n + left( frac{1}{2}+frac{5 sqrt {21}}{42} right)left( frac{3 + sqrt {21}}{2} right)^n$$



Happy to elaborate on any of the detail if necessary.






share|cite|improve this answer









$endgroup$









  • 1




    $begingroup$
    oh wow, yeah, I totally just wrote down the wrong sign somehow. thank you very much !!
    $endgroup$
    – Esther Rose
    49 mins ago



















2












$begingroup$

For situations involving linear, homogenous recurrence relations, the characteristic polynomial method works best.





Let us have the recurrence relation, for constants $c_i$ and $k>0$,



$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_{n} a_{n-k}$$



Much like with ordinary differential equations, we develop a characteristic polynomial for $a_n$. Let $a_n = alpha^n$. Then we get



$$alpha^n = c_1 alpha^{n-1} + c_2 alpha^{n-2} + ... + c_{k} alpha^{n-k}$$



Divide through by $alpha^{n-k}$ next:



$$alpha^{k} = c_1 alpha^{k-1} + c_2 alpha^{k-2} + ... + c_{k}$$



Bring everything to the same side:



$$alpha^{k} - c_1 alpha^{k-1} - c_2 alpha^{k-2} - ... - c_{k} = 0$$



This is a polynomial, and we seek the roots to it. Let them be $alpha_1,...,alpha_k$. (If $alpha_i$ is a duplicate root, replace the first duplicate with $nalpha_i$, the second with $n^2 alpha_k$, and so on.)



Then, for these roots, up to constants $A_1,...,A_k$ depending on your initial conditions, we have



$$a_n = A_1 alpha_1^n + ... + A_k alpha_k^n$$





Footnotes & Caveats:



As you might imagine, it is hypothetically possible for the recurrence to have complex roots. I do not know how to handle those situations since, as I noted in a few past answers, I'm taking a combinatorics class this semester and this stuff is relatively new to me, so I'm guessing they're keeping us to the "basic" stuff. They might do the same for you, I don't know. It probably depends on the class/text whether the examples are "nice enough" in that respect.



Also, a nice tidbit: it's a good paranoia check to double-check your solution. Once you have the explicit form for $a_n$, check that your initial solutions are valid, and perhaps a few other values you obtain from the recurrence relation. In examples like this where you have to derive the recurrence relation yourself instead of simply being given it, you should be able to get some values by brute force for $n=1,2,3,$ and so on, for ever-how-many initial conditions you need to use. (You need as many initial conditions as there are previous values that determine $a_n$.)



Also bear in mind that this method only works for linear, homogenous recurrence relations. For nonhomogenous ones, I've spoken to you on solving them. For nonlinear ones, we need something more elaborate (such as generating functions) but such discussion is well beyond the scope of this post.





A simple example to motivate this method:




Example: Let us find the solution to the Fibonacci recurrence
$$a_n = a_{n-1} + a_{n-2}$$
where $a_0 = 0,$ and $a_1 = 1$.




(Bear in mind that while here each $a_{text{something}}$ has coefficient $1$, they need not be, and as in the previous explanation the coefficients "carry over" to the characteristic polynomial. The Fibonacci relation is simply a common first example.)



Here, the characteristic polynomial is given by



$$alpha^n = alpha^{n-1} + alpha^{n-2}$$



Divide through by $alpha^{n-2}$:



$$alpha^2 = alpha + 1 implies alpha^2 - alpha - 1 = 0$$



This quadratic can be solved by the quadratic formula. It's a well known result that the two roots to this are the golden ratio $varphi$ and its conjugate $overline varphi$:



$$varphi = frac{1 + sqrt 5}{2} ;;;;; overline varphi = frac{1 - sqrt 5}{2}$$



Thus, up to constants $A_1,A_2$, we can claim



$$a_n = A_1 varphi ^n + A_2 overline{varphi}^n = A_1 left( frac{1 + sqrt 5}{2} right)^n + A_2 left( frac{1 - sqrt 5}{2} right)^n$$



What remains is to determine the constants $A_1, A_2$. To do this, substitute your initial conditions. Thus, you get a system of equations as below. In $a_0$, you let $n=0$ in your solution for $a_n$ above; similarly, $n=1$ in the $a_1$ case.



$$left{begin{matrix}
a_0 = 0\
a_1 = 1
end{matrix}right. implies left{begin{matrix}
A_1 + A_2 = 0\
A_1 varphi + A_2 overline{varphi} = 1
end{matrix}right.$$



To solve this is a fairly typical exercise in solving systems of equations, or linear algebra if you're faced with the awful situation of many initial conditions. I'll skip the boring bits, leaving the algebra to you, simply saying you should get $A_1 = 1/sqrt 5, A_2 = -1/sqrt5$.



And thus we get a general formula for the Fibonacci relation!



$$a_n = frac{ varphi ^n}{sqrt 5} - frac{overline{varphi}^n}{sqrt 5} = frac{ 1}{sqrt 5}left(frac{1 + sqrt 5}{2}right)^n - frac{1}{sqrt 5}left( frac{1 + sqrt 5}{2} right)^n$$






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Short answer for what happens in the case of complex roots: The same analysis goes through, and you get a formula of the form $a_n = a_1 lambda_1^n + cdots + a_k lambda_k^n$ with $lambda_i$ complex that nevertheless is real for all $n$. (The same complication for repeated roots also applies.)
    $endgroup$
    – anomaly
    43 mins ago








  • 1




    $begingroup$
    Huh. That's actually pretty surprising, though I suppose it makes sense. O_o Thanks for letting me know.
    $endgroup$
    – Eevee Trainer
    41 mins ago





















1












$begingroup$

By induction, your recurrence relation can be written as
$$begin{pmatrix}
a_n\
a_{n-1}
end{pmatrix}
=
begin{pmatrix}
3&-3\
0&1
end{pmatrix}
begin{pmatrix}
a_{n-1}\
a_{n-2}
end{pmatrix}
=
begin{pmatrix}
3&-3\
0&1
end{pmatrix}^{n-1}
begin{pmatrix}
a_1\
a_0
end{pmatrix}
.$$

The Jordan decomposition of this matrix allows for simple closed forms for the coefficients of the powers of this matrix.






share|cite|improve this answer









$endgroup$





















    0












    $begingroup$

    Whenever you have a recurrence relation of the form $u_{n+2}=alpha u_{n+1}+beta u_n$, you want to find a basis of the set of solutions. One good idea is to look for geometric sequences. If $r$ is the rate, then $r$ verifies
    $$r^2=alpha r+beta$$
    If $r_1$ and $r_2$ are the (complex) solutions, then every sequence is of the form
    $$u_n=Ar_1^n+Br_2^n$$
    and you find $A$ and $B$ by looking at the initial values.






    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%2f3173931%2fsolving-a-recurrence-relation-poker-chips%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      1












      $begingroup$

      Thanks for an interesting question.



      The recurrence relation given in the question is not correct, albeit with only a sign error.



      It should be;
      $$a_n=3a_{n-1}+3a_{n-2}$$
      $$a_0=1 : a_1=4$$
      This gives rise to the generating series,
      $$1+4x+15x^2+57x^3+216x^4+819x^5+dots+169209x^9+641520x^{10}+2432187x^{11}+dots$$
      So, assuming the initial term is $a_0$, $a_{10}=641520$, which you asked for.



      This generating series has generating function,
      $$frac{1+x}{1-3x-3x^2}$$
      Applying partial fractions to this gives, after some algebra,
      $$frac{1+x}{1-3x-3x^2}=frac{21-5 sqrt{21}}{42 big( 1-frac{3-sqrt{21}}{2}x big)}+frac{21+5 sqrt{21}}{42 big( 1-frac{3+sqrt{21}}{2}x big)}$$
      which are recognisable as standard bits directly translating into a formula for the $n^{th}$ term,
      $$T_n=left( frac{1}{2}-frac{5 sqrt {21}}{42} right)left( frac{3 - sqrt {21}}{2} right)^n + left( frac{1}{2}+frac{5 sqrt {21}}{42} right)left( frac{3 + sqrt {21}}{2} right)^n$$



      Happy to elaborate on any of the detail if necessary.






      share|cite|improve this answer









      $endgroup$









      • 1




        $begingroup$
        oh wow, yeah, I totally just wrote down the wrong sign somehow. thank you very much !!
        $endgroup$
        – Esther Rose
        49 mins ago
















      1












      $begingroup$

      Thanks for an interesting question.



      The recurrence relation given in the question is not correct, albeit with only a sign error.



      It should be;
      $$a_n=3a_{n-1}+3a_{n-2}$$
      $$a_0=1 : a_1=4$$
      This gives rise to the generating series,
      $$1+4x+15x^2+57x^3+216x^4+819x^5+dots+169209x^9+641520x^{10}+2432187x^{11}+dots$$
      So, assuming the initial term is $a_0$, $a_{10}=641520$, which you asked for.



      This generating series has generating function,
      $$frac{1+x}{1-3x-3x^2}$$
      Applying partial fractions to this gives, after some algebra,
      $$frac{1+x}{1-3x-3x^2}=frac{21-5 sqrt{21}}{42 big( 1-frac{3-sqrt{21}}{2}x big)}+frac{21+5 sqrt{21}}{42 big( 1-frac{3+sqrt{21}}{2}x big)}$$
      which are recognisable as standard bits directly translating into a formula for the $n^{th}$ term,
      $$T_n=left( frac{1}{2}-frac{5 sqrt {21}}{42} right)left( frac{3 - sqrt {21}}{2} right)^n + left( frac{1}{2}+frac{5 sqrt {21}}{42} right)left( frac{3 + sqrt {21}}{2} right)^n$$



      Happy to elaborate on any of the detail if necessary.






      share|cite|improve this answer









      $endgroup$









      • 1




        $begingroup$
        oh wow, yeah, I totally just wrote down the wrong sign somehow. thank you very much !!
        $endgroup$
        – Esther Rose
        49 mins ago














      1












      1








      1





      $begingroup$

      Thanks for an interesting question.



      The recurrence relation given in the question is not correct, albeit with only a sign error.



      It should be;
      $$a_n=3a_{n-1}+3a_{n-2}$$
      $$a_0=1 : a_1=4$$
      This gives rise to the generating series,
      $$1+4x+15x^2+57x^3+216x^4+819x^5+dots+169209x^9+641520x^{10}+2432187x^{11}+dots$$
      So, assuming the initial term is $a_0$, $a_{10}=641520$, which you asked for.



      This generating series has generating function,
      $$frac{1+x}{1-3x-3x^2}$$
      Applying partial fractions to this gives, after some algebra,
      $$frac{1+x}{1-3x-3x^2}=frac{21-5 sqrt{21}}{42 big( 1-frac{3-sqrt{21}}{2}x big)}+frac{21+5 sqrt{21}}{42 big( 1-frac{3+sqrt{21}}{2}x big)}$$
      which are recognisable as standard bits directly translating into a formula for the $n^{th}$ term,
      $$T_n=left( frac{1}{2}-frac{5 sqrt {21}}{42} right)left( frac{3 - sqrt {21}}{2} right)^n + left( frac{1}{2}+frac{5 sqrt {21}}{42} right)left( frac{3 + sqrt {21}}{2} right)^n$$



      Happy to elaborate on any of the detail if necessary.






      share|cite|improve this answer









      $endgroup$



      Thanks for an interesting question.



      The recurrence relation given in the question is not correct, albeit with only a sign error.



      It should be;
      $$a_n=3a_{n-1}+3a_{n-2}$$
      $$a_0=1 : a_1=4$$
      This gives rise to the generating series,
      $$1+4x+15x^2+57x^3+216x^4+819x^5+dots+169209x^9+641520x^{10}+2432187x^{11}+dots$$
      So, assuming the initial term is $a_0$, $a_{10}=641520$, which you asked for.



      This generating series has generating function,
      $$frac{1+x}{1-3x-3x^2}$$
      Applying partial fractions to this gives, after some algebra,
      $$frac{1+x}{1-3x-3x^2}=frac{21-5 sqrt{21}}{42 big( 1-frac{3-sqrt{21}}{2}x big)}+frac{21+5 sqrt{21}}{42 big( 1-frac{3+sqrt{21}}{2}x big)}$$
      which are recognisable as standard bits directly translating into a formula for the $n^{th}$ term,
      $$T_n=left( frac{1}{2}-frac{5 sqrt {21}}{42} right)left( frac{3 - sqrt {21}}{2} right)^n + left( frac{1}{2}+frac{5 sqrt {21}}{42} right)left( frac{3 + sqrt {21}}{2} right)^n$$



      Happy to elaborate on any of the detail if necessary.







      share|cite|improve this answer












      share|cite|improve this answer



      share|cite|improve this answer










      answered 1 hour ago









      Martin HansenMartin Hansen

      770114




      770114








      • 1




        $begingroup$
        oh wow, yeah, I totally just wrote down the wrong sign somehow. thank you very much !!
        $endgroup$
        – Esther Rose
        49 mins ago














      • 1




        $begingroup$
        oh wow, yeah, I totally just wrote down the wrong sign somehow. thank you very much !!
        $endgroup$
        – Esther Rose
        49 mins ago








      1




      1




      $begingroup$
      oh wow, yeah, I totally just wrote down the wrong sign somehow. thank you very much !!
      $endgroup$
      – Esther Rose
      49 mins ago




      $begingroup$
      oh wow, yeah, I totally just wrote down the wrong sign somehow. thank you very much !!
      $endgroup$
      – Esther Rose
      49 mins ago











      2












      $begingroup$

      For situations involving linear, homogenous recurrence relations, the characteristic polynomial method works best.





      Let us have the recurrence relation, for constants $c_i$ and $k>0$,



      $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_{n} a_{n-k}$$



      Much like with ordinary differential equations, we develop a characteristic polynomial for $a_n$. Let $a_n = alpha^n$. Then we get



      $$alpha^n = c_1 alpha^{n-1} + c_2 alpha^{n-2} + ... + c_{k} alpha^{n-k}$$



      Divide through by $alpha^{n-k}$ next:



      $$alpha^{k} = c_1 alpha^{k-1} + c_2 alpha^{k-2} + ... + c_{k}$$



      Bring everything to the same side:



      $$alpha^{k} - c_1 alpha^{k-1} - c_2 alpha^{k-2} - ... - c_{k} = 0$$



      This is a polynomial, and we seek the roots to it. Let them be $alpha_1,...,alpha_k$. (If $alpha_i$ is a duplicate root, replace the first duplicate with $nalpha_i$, the second with $n^2 alpha_k$, and so on.)



      Then, for these roots, up to constants $A_1,...,A_k$ depending on your initial conditions, we have



      $$a_n = A_1 alpha_1^n + ... + A_k alpha_k^n$$





      Footnotes & Caveats:



      As you might imagine, it is hypothetically possible for the recurrence to have complex roots. I do not know how to handle those situations since, as I noted in a few past answers, I'm taking a combinatorics class this semester and this stuff is relatively new to me, so I'm guessing they're keeping us to the "basic" stuff. They might do the same for you, I don't know. It probably depends on the class/text whether the examples are "nice enough" in that respect.



      Also, a nice tidbit: it's a good paranoia check to double-check your solution. Once you have the explicit form for $a_n$, check that your initial solutions are valid, and perhaps a few other values you obtain from the recurrence relation. In examples like this where you have to derive the recurrence relation yourself instead of simply being given it, you should be able to get some values by brute force for $n=1,2,3,$ and so on, for ever-how-many initial conditions you need to use. (You need as many initial conditions as there are previous values that determine $a_n$.)



      Also bear in mind that this method only works for linear, homogenous recurrence relations. For nonhomogenous ones, I've spoken to you on solving them. For nonlinear ones, we need something more elaborate (such as generating functions) but such discussion is well beyond the scope of this post.





      A simple example to motivate this method:




      Example: Let us find the solution to the Fibonacci recurrence
      $$a_n = a_{n-1} + a_{n-2}$$
      where $a_0 = 0,$ and $a_1 = 1$.




      (Bear in mind that while here each $a_{text{something}}$ has coefficient $1$, they need not be, and as in the previous explanation the coefficients "carry over" to the characteristic polynomial. The Fibonacci relation is simply a common first example.)



      Here, the characteristic polynomial is given by



      $$alpha^n = alpha^{n-1} + alpha^{n-2}$$



      Divide through by $alpha^{n-2}$:



      $$alpha^2 = alpha + 1 implies alpha^2 - alpha - 1 = 0$$



      This quadratic can be solved by the quadratic formula. It's a well known result that the two roots to this are the golden ratio $varphi$ and its conjugate $overline varphi$:



      $$varphi = frac{1 + sqrt 5}{2} ;;;;; overline varphi = frac{1 - sqrt 5}{2}$$



      Thus, up to constants $A_1,A_2$, we can claim



      $$a_n = A_1 varphi ^n + A_2 overline{varphi}^n = A_1 left( frac{1 + sqrt 5}{2} right)^n + A_2 left( frac{1 - sqrt 5}{2} right)^n$$



      What remains is to determine the constants $A_1, A_2$. To do this, substitute your initial conditions. Thus, you get a system of equations as below. In $a_0$, you let $n=0$ in your solution for $a_n$ above; similarly, $n=1$ in the $a_1$ case.



      $$left{begin{matrix}
      a_0 = 0\
      a_1 = 1
      end{matrix}right. implies left{begin{matrix}
      A_1 + A_2 = 0\
      A_1 varphi + A_2 overline{varphi} = 1
      end{matrix}right.$$



      To solve this is a fairly typical exercise in solving systems of equations, or linear algebra if you're faced with the awful situation of many initial conditions. I'll skip the boring bits, leaving the algebra to you, simply saying you should get $A_1 = 1/sqrt 5, A_2 = -1/sqrt5$.



      And thus we get a general formula for the Fibonacci relation!



      $$a_n = frac{ varphi ^n}{sqrt 5} - frac{overline{varphi}^n}{sqrt 5} = frac{ 1}{sqrt 5}left(frac{1 + sqrt 5}{2}right)^n - frac{1}{sqrt 5}left( frac{1 + sqrt 5}{2} right)^n$$






      share|cite|improve this answer









      $endgroup$













      • $begingroup$
        Short answer for what happens in the case of complex roots: The same analysis goes through, and you get a formula of the form $a_n = a_1 lambda_1^n + cdots + a_k lambda_k^n$ with $lambda_i$ complex that nevertheless is real for all $n$. (The same complication for repeated roots also applies.)
        $endgroup$
        – anomaly
        43 mins ago








      • 1




        $begingroup$
        Huh. That's actually pretty surprising, though I suppose it makes sense. O_o Thanks for letting me know.
        $endgroup$
        – Eevee Trainer
        41 mins ago


















      2












      $begingroup$

      For situations involving linear, homogenous recurrence relations, the characteristic polynomial method works best.





      Let us have the recurrence relation, for constants $c_i$ and $k>0$,



      $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_{n} a_{n-k}$$



      Much like with ordinary differential equations, we develop a characteristic polynomial for $a_n$. Let $a_n = alpha^n$. Then we get



      $$alpha^n = c_1 alpha^{n-1} + c_2 alpha^{n-2} + ... + c_{k} alpha^{n-k}$$



      Divide through by $alpha^{n-k}$ next:



      $$alpha^{k} = c_1 alpha^{k-1} + c_2 alpha^{k-2} + ... + c_{k}$$



      Bring everything to the same side:



      $$alpha^{k} - c_1 alpha^{k-1} - c_2 alpha^{k-2} - ... - c_{k} = 0$$



      This is a polynomial, and we seek the roots to it. Let them be $alpha_1,...,alpha_k$. (If $alpha_i$ is a duplicate root, replace the first duplicate with $nalpha_i$, the second with $n^2 alpha_k$, and so on.)



      Then, for these roots, up to constants $A_1,...,A_k$ depending on your initial conditions, we have



      $$a_n = A_1 alpha_1^n + ... + A_k alpha_k^n$$





      Footnotes & Caveats:



      As you might imagine, it is hypothetically possible for the recurrence to have complex roots. I do not know how to handle those situations since, as I noted in a few past answers, I'm taking a combinatorics class this semester and this stuff is relatively new to me, so I'm guessing they're keeping us to the "basic" stuff. They might do the same for you, I don't know. It probably depends on the class/text whether the examples are "nice enough" in that respect.



      Also, a nice tidbit: it's a good paranoia check to double-check your solution. Once you have the explicit form for $a_n$, check that your initial solutions are valid, and perhaps a few other values you obtain from the recurrence relation. In examples like this where you have to derive the recurrence relation yourself instead of simply being given it, you should be able to get some values by brute force for $n=1,2,3,$ and so on, for ever-how-many initial conditions you need to use. (You need as many initial conditions as there are previous values that determine $a_n$.)



      Also bear in mind that this method only works for linear, homogenous recurrence relations. For nonhomogenous ones, I've spoken to you on solving them. For nonlinear ones, we need something more elaborate (such as generating functions) but such discussion is well beyond the scope of this post.





      A simple example to motivate this method:




      Example: Let us find the solution to the Fibonacci recurrence
      $$a_n = a_{n-1} + a_{n-2}$$
      where $a_0 = 0,$ and $a_1 = 1$.




      (Bear in mind that while here each $a_{text{something}}$ has coefficient $1$, they need not be, and as in the previous explanation the coefficients "carry over" to the characteristic polynomial. The Fibonacci relation is simply a common first example.)



      Here, the characteristic polynomial is given by



      $$alpha^n = alpha^{n-1} + alpha^{n-2}$$



      Divide through by $alpha^{n-2}$:



      $$alpha^2 = alpha + 1 implies alpha^2 - alpha - 1 = 0$$



      This quadratic can be solved by the quadratic formula. It's a well known result that the two roots to this are the golden ratio $varphi$ and its conjugate $overline varphi$:



      $$varphi = frac{1 + sqrt 5}{2} ;;;;; overline varphi = frac{1 - sqrt 5}{2}$$



      Thus, up to constants $A_1,A_2$, we can claim



      $$a_n = A_1 varphi ^n + A_2 overline{varphi}^n = A_1 left( frac{1 + sqrt 5}{2} right)^n + A_2 left( frac{1 - sqrt 5}{2} right)^n$$



      What remains is to determine the constants $A_1, A_2$. To do this, substitute your initial conditions. Thus, you get a system of equations as below. In $a_0$, you let $n=0$ in your solution for $a_n$ above; similarly, $n=1$ in the $a_1$ case.



      $$left{begin{matrix}
      a_0 = 0\
      a_1 = 1
      end{matrix}right. implies left{begin{matrix}
      A_1 + A_2 = 0\
      A_1 varphi + A_2 overline{varphi} = 1
      end{matrix}right.$$



      To solve this is a fairly typical exercise in solving systems of equations, or linear algebra if you're faced with the awful situation of many initial conditions. I'll skip the boring bits, leaving the algebra to you, simply saying you should get $A_1 = 1/sqrt 5, A_2 = -1/sqrt5$.



      And thus we get a general formula for the Fibonacci relation!



      $$a_n = frac{ varphi ^n}{sqrt 5} - frac{overline{varphi}^n}{sqrt 5} = frac{ 1}{sqrt 5}left(frac{1 + sqrt 5}{2}right)^n - frac{1}{sqrt 5}left( frac{1 + sqrt 5}{2} right)^n$$






      share|cite|improve this answer









      $endgroup$













      • $begingroup$
        Short answer for what happens in the case of complex roots: The same analysis goes through, and you get a formula of the form $a_n = a_1 lambda_1^n + cdots + a_k lambda_k^n$ with $lambda_i$ complex that nevertheless is real for all $n$. (The same complication for repeated roots also applies.)
        $endgroup$
        – anomaly
        43 mins ago








      • 1




        $begingroup$
        Huh. That's actually pretty surprising, though I suppose it makes sense. O_o Thanks for letting me know.
        $endgroup$
        – Eevee Trainer
        41 mins ago
















      2












      2








      2





      $begingroup$

      For situations involving linear, homogenous recurrence relations, the characteristic polynomial method works best.





      Let us have the recurrence relation, for constants $c_i$ and $k>0$,



      $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_{n} a_{n-k}$$



      Much like with ordinary differential equations, we develop a characteristic polynomial for $a_n$. Let $a_n = alpha^n$. Then we get



      $$alpha^n = c_1 alpha^{n-1} + c_2 alpha^{n-2} + ... + c_{k} alpha^{n-k}$$



      Divide through by $alpha^{n-k}$ next:



      $$alpha^{k} = c_1 alpha^{k-1} + c_2 alpha^{k-2} + ... + c_{k}$$



      Bring everything to the same side:



      $$alpha^{k} - c_1 alpha^{k-1} - c_2 alpha^{k-2} - ... - c_{k} = 0$$



      This is a polynomial, and we seek the roots to it. Let them be $alpha_1,...,alpha_k$. (If $alpha_i$ is a duplicate root, replace the first duplicate with $nalpha_i$, the second with $n^2 alpha_k$, and so on.)



      Then, for these roots, up to constants $A_1,...,A_k$ depending on your initial conditions, we have



      $$a_n = A_1 alpha_1^n + ... + A_k alpha_k^n$$





      Footnotes & Caveats:



      As you might imagine, it is hypothetically possible for the recurrence to have complex roots. I do not know how to handle those situations since, as I noted in a few past answers, I'm taking a combinatorics class this semester and this stuff is relatively new to me, so I'm guessing they're keeping us to the "basic" stuff. They might do the same for you, I don't know. It probably depends on the class/text whether the examples are "nice enough" in that respect.



      Also, a nice tidbit: it's a good paranoia check to double-check your solution. Once you have the explicit form for $a_n$, check that your initial solutions are valid, and perhaps a few other values you obtain from the recurrence relation. In examples like this where you have to derive the recurrence relation yourself instead of simply being given it, you should be able to get some values by brute force for $n=1,2,3,$ and so on, for ever-how-many initial conditions you need to use. (You need as many initial conditions as there are previous values that determine $a_n$.)



      Also bear in mind that this method only works for linear, homogenous recurrence relations. For nonhomogenous ones, I've spoken to you on solving them. For nonlinear ones, we need something more elaborate (such as generating functions) but such discussion is well beyond the scope of this post.





      A simple example to motivate this method:




      Example: Let us find the solution to the Fibonacci recurrence
      $$a_n = a_{n-1} + a_{n-2}$$
      where $a_0 = 0,$ and $a_1 = 1$.




      (Bear in mind that while here each $a_{text{something}}$ has coefficient $1$, they need not be, and as in the previous explanation the coefficients "carry over" to the characteristic polynomial. The Fibonacci relation is simply a common first example.)



      Here, the characteristic polynomial is given by



      $$alpha^n = alpha^{n-1} + alpha^{n-2}$$



      Divide through by $alpha^{n-2}$:



      $$alpha^2 = alpha + 1 implies alpha^2 - alpha - 1 = 0$$



      This quadratic can be solved by the quadratic formula. It's a well known result that the two roots to this are the golden ratio $varphi$ and its conjugate $overline varphi$:



      $$varphi = frac{1 + sqrt 5}{2} ;;;;; overline varphi = frac{1 - sqrt 5}{2}$$



      Thus, up to constants $A_1,A_2$, we can claim



      $$a_n = A_1 varphi ^n + A_2 overline{varphi}^n = A_1 left( frac{1 + sqrt 5}{2} right)^n + A_2 left( frac{1 - sqrt 5}{2} right)^n$$



      What remains is to determine the constants $A_1, A_2$. To do this, substitute your initial conditions. Thus, you get a system of equations as below. In $a_0$, you let $n=0$ in your solution for $a_n$ above; similarly, $n=1$ in the $a_1$ case.



      $$left{begin{matrix}
      a_0 = 0\
      a_1 = 1
      end{matrix}right. implies left{begin{matrix}
      A_1 + A_2 = 0\
      A_1 varphi + A_2 overline{varphi} = 1
      end{matrix}right.$$



      To solve this is a fairly typical exercise in solving systems of equations, or linear algebra if you're faced with the awful situation of many initial conditions. I'll skip the boring bits, leaving the algebra to you, simply saying you should get $A_1 = 1/sqrt 5, A_2 = -1/sqrt5$.



      And thus we get a general formula for the Fibonacci relation!



      $$a_n = frac{ varphi ^n}{sqrt 5} - frac{overline{varphi}^n}{sqrt 5} = frac{ 1}{sqrt 5}left(frac{1 + sqrt 5}{2}right)^n - frac{1}{sqrt 5}left( frac{1 + sqrt 5}{2} right)^n$$






      share|cite|improve this answer









      $endgroup$



      For situations involving linear, homogenous recurrence relations, the characteristic polynomial method works best.





      Let us have the recurrence relation, for constants $c_i$ and $k>0$,



      $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_{n} a_{n-k}$$



      Much like with ordinary differential equations, we develop a characteristic polynomial for $a_n$. Let $a_n = alpha^n$. Then we get



      $$alpha^n = c_1 alpha^{n-1} + c_2 alpha^{n-2} + ... + c_{k} alpha^{n-k}$$



      Divide through by $alpha^{n-k}$ next:



      $$alpha^{k} = c_1 alpha^{k-1} + c_2 alpha^{k-2} + ... + c_{k}$$



      Bring everything to the same side:



      $$alpha^{k} - c_1 alpha^{k-1} - c_2 alpha^{k-2} - ... - c_{k} = 0$$



      This is a polynomial, and we seek the roots to it. Let them be $alpha_1,...,alpha_k$. (If $alpha_i$ is a duplicate root, replace the first duplicate with $nalpha_i$, the second with $n^2 alpha_k$, and so on.)



      Then, for these roots, up to constants $A_1,...,A_k$ depending on your initial conditions, we have



      $$a_n = A_1 alpha_1^n + ... + A_k alpha_k^n$$





      Footnotes & Caveats:



      As you might imagine, it is hypothetically possible for the recurrence to have complex roots. I do not know how to handle those situations since, as I noted in a few past answers, I'm taking a combinatorics class this semester and this stuff is relatively new to me, so I'm guessing they're keeping us to the "basic" stuff. They might do the same for you, I don't know. It probably depends on the class/text whether the examples are "nice enough" in that respect.



      Also, a nice tidbit: it's a good paranoia check to double-check your solution. Once you have the explicit form for $a_n$, check that your initial solutions are valid, and perhaps a few other values you obtain from the recurrence relation. In examples like this where you have to derive the recurrence relation yourself instead of simply being given it, you should be able to get some values by brute force for $n=1,2,3,$ and so on, for ever-how-many initial conditions you need to use. (You need as many initial conditions as there are previous values that determine $a_n$.)



      Also bear in mind that this method only works for linear, homogenous recurrence relations. For nonhomogenous ones, I've spoken to you on solving them. For nonlinear ones, we need something more elaborate (such as generating functions) but such discussion is well beyond the scope of this post.





      A simple example to motivate this method:




      Example: Let us find the solution to the Fibonacci recurrence
      $$a_n = a_{n-1} + a_{n-2}$$
      where $a_0 = 0,$ and $a_1 = 1$.




      (Bear in mind that while here each $a_{text{something}}$ has coefficient $1$, they need not be, and as in the previous explanation the coefficients "carry over" to the characteristic polynomial. The Fibonacci relation is simply a common first example.)



      Here, the characteristic polynomial is given by



      $$alpha^n = alpha^{n-1} + alpha^{n-2}$$



      Divide through by $alpha^{n-2}$:



      $$alpha^2 = alpha + 1 implies alpha^2 - alpha - 1 = 0$$



      This quadratic can be solved by the quadratic formula. It's a well known result that the two roots to this are the golden ratio $varphi$ and its conjugate $overline varphi$:



      $$varphi = frac{1 + sqrt 5}{2} ;;;;; overline varphi = frac{1 - sqrt 5}{2}$$



      Thus, up to constants $A_1,A_2$, we can claim



      $$a_n = A_1 varphi ^n + A_2 overline{varphi}^n = A_1 left( frac{1 + sqrt 5}{2} right)^n + A_2 left( frac{1 - sqrt 5}{2} right)^n$$



      What remains is to determine the constants $A_1, A_2$. To do this, substitute your initial conditions. Thus, you get a system of equations as below. In $a_0$, you let $n=0$ in your solution for $a_n$ above; similarly, $n=1$ in the $a_1$ case.



      $$left{begin{matrix}
      a_0 = 0\
      a_1 = 1
      end{matrix}right. implies left{begin{matrix}
      A_1 + A_2 = 0\
      A_1 varphi + A_2 overline{varphi} = 1
      end{matrix}right.$$



      To solve this is a fairly typical exercise in solving systems of equations, or linear algebra if you're faced with the awful situation of many initial conditions. I'll skip the boring bits, leaving the algebra to you, simply saying you should get $A_1 = 1/sqrt 5, A_2 = -1/sqrt5$.



      And thus we get a general formula for the Fibonacci relation!



      $$a_n = frac{ varphi ^n}{sqrt 5} - frac{overline{varphi}^n}{sqrt 5} = frac{ 1}{sqrt 5}left(frac{1 + sqrt 5}{2}right)^n - frac{1}{sqrt 5}left( frac{1 + sqrt 5}{2} right)^n$$







      share|cite|improve this answer












      share|cite|improve this answer



      share|cite|improve this answer










      answered 3 hours ago









      Eevee TrainerEevee Trainer

      9,51331740




      9,51331740












      • $begingroup$
        Short answer for what happens in the case of complex roots: The same analysis goes through, and you get a formula of the form $a_n = a_1 lambda_1^n + cdots + a_k lambda_k^n$ with $lambda_i$ complex that nevertheless is real for all $n$. (The same complication for repeated roots also applies.)
        $endgroup$
        – anomaly
        43 mins ago








      • 1




        $begingroup$
        Huh. That's actually pretty surprising, though I suppose it makes sense. O_o Thanks for letting me know.
        $endgroup$
        – Eevee Trainer
        41 mins ago




















      • $begingroup$
        Short answer for what happens in the case of complex roots: The same analysis goes through, and you get a formula of the form $a_n = a_1 lambda_1^n + cdots + a_k lambda_k^n$ with $lambda_i$ complex that nevertheless is real for all $n$. (The same complication for repeated roots also applies.)
        $endgroup$
        – anomaly
        43 mins ago








      • 1




        $begingroup$
        Huh. That's actually pretty surprising, though I suppose it makes sense. O_o Thanks for letting me know.
        $endgroup$
        – Eevee Trainer
        41 mins ago


















      $begingroup$
      Short answer for what happens in the case of complex roots: The same analysis goes through, and you get a formula of the form $a_n = a_1 lambda_1^n + cdots + a_k lambda_k^n$ with $lambda_i$ complex that nevertheless is real for all $n$. (The same complication for repeated roots also applies.)
      $endgroup$
      – anomaly
      43 mins ago






      $begingroup$
      Short answer for what happens in the case of complex roots: The same analysis goes through, and you get a formula of the form $a_n = a_1 lambda_1^n + cdots + a_k lambda_k^n$ with $lambda_i$ complex that nevertheless is real for all $n$. (The same complication for repeated roots also applies.)
      $endgroup$
      – anomaly
      43 mins ago






      1




      1




      $begingroup$
      Huh. That's actually pretty surprising, though I suppose it makes sense. O_o Thanks for letting me know.
      $endgroup$
      – Eevee Trainer
      41 mins ago






      $begingroup$
      Huh. That's actually pretty surprising, though I suppose it makes sense. O_o Thanks for letting me know.
      $endgroup$
      – Eevee Trainer
      41 mins ago













      1












      $begingroup$

      By induction, your recurrence relation can be written as
      $$begin{pmatrix}
      a_n\
      a_{n-1}
      end{pmatrix}
      =
      begin{pmatrix}
      3&-3\
      0&1
      end{pmatrix}
      begin{pmatrix}
      a_{n-1}\
      a_{n-2}
      end{pmatrix}
      =
      begin{pmatrix}
      3&-3\
      0&1
      end{pmatrix}^{n-1}
      begin{pmatrix}
      a_1\
      a_0
      end{pmatrix}
      .$$

      The Jordan decomposition of this matrix allows for simple closed forms for the coefficients of the powers of this matrix.






      share|cite|improve this answer









      $endgroup$


















        1












        $begingroup$

        By induction, your recurrence relation can be written as
        $$begin{pmatrix}
        a_n\
        a_{n-1}
        end{pmatrix}
        =
        begin{pmatrix}
        3&-3\
        0&1
        end{pmatrix}
        begin{pmatrix}
        a_{n-1}\
        a_{n-2}
        end{pmatrix}
        =
        begin{pmatrix}
        3&-3\
        0&1
        end{pmatrix}^{n-1}
        begin{pmatrix}
        a_1\
        a_0
        end{pmatrix}
        .$$

        The Jordan decomposition of this matrix allows for simple closed forms for the coefficients of the powers of this matrix.






        share|cite|improve this answer









        $endgroup$
















          1












          1








          1





          $begingroup$

          By induction, your recurrence relation can be written as
          $$begin{pmatrix}
          a_n\
          a_{n-1}
          end{pmatrix}
          =
          begin{pmatrix}
          3&-3\
          0&1
          end{pmatrix}
          begin{pmatrix}
          a_{n-1}\
          a_{n-2}
          end{pmatrix}
          =
          begin{pmatrix}
          3&-3\
          0&1
          end{pmatrix}^{n-1}
          begin{pmatrix}
          a_1\
          a_0
          end{pmatrix}
          .$$

          The Jordan decomposition of this matrix allows for simple closed forms for the coefficients of the powers of this matrix.






          share|cite|improve this answer









          $endgroup$



          By induction, your recurrence relation can be written as
          $$begin{pmatrix}
          a_n\
          a_{n-1}
          end{pmatrix}
          =
          begin{pmatrix}
          3&-3\
          0&1
          end{pmatrix}
          begin{pmatrix}
          a_{n-1}\
          a_{n-2}
          end{pmatrix}
          =
          begin{pmatrix}
          3&-3\
          0&1
          end{pmatrix}^{n-1}
          begin{pmatrix}
          a_1\
          a_0
          end{pmatrix}
          .$$

          The Jordan decomposition of this matrix allows for simple closed forms for the coefficients of the powers of this matrix.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 3 hours ago









          ServaesServaes

          29.6k342101




          29.6k342101























              0












              $begingroup$

              Whenever you have a recurrence relation of the form $u_{n+2}=alpha u_{n+1}+beta u_n$, you want to find a basis of the set of solutions. One good idea is to look for geometric sequences. If $r$ is the rate, then $r$ verifies
              $$r^2=alpha r+beta$$
              If $r_1$ and $r_2$ are the (complex) solutions, then every sequence is of the form
              $$u_n=Ar_1^n+Br_2^n$$
              and you find $A$ and $B$ by looking at the initial values.






              share|cite|improve this answer









              $endgroup$


















                0












                $begingroup$

                Whenever you have a recurrence relation of the form $u_{n+2}=alpha u_{n+1}+beta u_n$, you want to find a basis of the set of solutions. One good idea is to look for geometric sequences. If $r$ is the rate, then $r$ verifies
                $$r^2=alpha r+beta$$
                If $r_1$ and $r_2$ are the (complex) solutions, then every sequence is of the form
                $$u_n=Ar_1^n+Br_2^n$$
                and you find $A$ and $B$ by looking at the initial values.






                share|cite|improve this answer









                $endgroup$
















                  0












                  0








                  0





                  $begingroup$

                  Whenever you have a recurrence relation of the form $u_{n+2}=alpha u_{n+1}+beta u_n$, you want to find a basis of the set of solutions. One good idea is to look for geometric sequences. If $r$ is the rate, then $r$ verifies
                  $$r^2=alpha r+beta$$
                  If $r_1$ and $r_2$ are the (complex) solutions, then every sequence is of the form
                  $$u_n=Ar_1^n+Br_2^n$$
                  and you find $A$ and $B$ by looking at the initial values.






                  share|cite|improve this answer









                  $endgroup$



                  Whenever you have a recurrence relation of the form $u_{n+2}=alpha u_{n+1}+beta u_n$, you want to find a basis of the set of solutions. One good idea is to look for geometric sequences. If $r$ is the rate, then $r$ verifies
                  $$r^2=alpha r+beta$$
                  If $r_1$ and $r_2$ are the (complex) solutions, then every sequence is of the form
                  $$u_n=Ar_1^n+Br_2^n$$
                  and you find $A$ and $B$ by looking at the initial values.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 3 hours ago









                  Nicolas FRANCOISNicolas FRANCOIS

                  3,7771516




                  3,7771516






























                      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%2f3173931%2fsolving-a-recurrence-relation-poker-chips%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

                      Couldn't open a raw socket. Error: Permission denied (13) (nmap)Is it possible to run networking commands...

                      VNC viewer RFB protocol error: bad desktop size 0x0I Cannot Type the Key 'd' (lowercase) in VNC Viewer...

                      Why not use the yoke to control yaw, as well as pitch and roll? Announcing the arrival of...