1

I'm trying to find the explicit formula for the recursion $a_n = 2a_{n-1} + a_{n-2}$ with $a_0 = 1$ and $a_1 = 3$. I already found the generating function: $f(x) = \frac{1+x}{1-2x-x^2}$, and the characteristic polynomial: $x^2 - 2x + 1 = 0$, which has the roots $1+√2$ and $1-√2$. What is the explicit formula for this recursion, and how do I find it?

Drew Weisserman
  • 35
  • 5
  • 1
    You have done almost everything. Roots of the characteristic polynomial are solutions of the recursion. Your solution is of the form

    $$a_n = c_1(1+\sqrt{2})^n + c_2(1-\sqrt{2})^n$$

    Plug in the initial values of $a_0$ and $a_1$ to get the values of the constants $c_1$ and $c_2$

     – Sauhard Sharma Jan 14 '19 at 07:35
  • @SauhardSharma Why are you answering in a comment? – Arthur Jan 14 '19 at 07:36
  • @Arthur Because I thought that he had done most of the work and required only a small nudge to get to the solution. – Sauhard Sharma Jan 14 '19 at 07:38
  • @SauhardSharma Thank you so much!!! – Drew Weisserman Jan 14 '19 at 07:38
  • @SauhardSharma That's still exactly what an answer post is for, and not at all what a comment is for. – Arthur Jan 14 '19 at 07:40
  • 1
    @Arthur Mea Culpa then. I won't do this from now on. Thanks for the advice !!! – Sauhard Sharma Jan 14 '19 at 07:42
  • One small problem: $x^2-2x+1=(x-1)^2$ is not the characteristic polynomial. Looks like you have a typo there. – amd Jan 14 '19 at 20:14

1 Answers1

2

Since the characteristic function has roots $1+\sqrt{2}$ and $1-\sqrt{2}$, the formula for the general term is $$a_n = A(1+\sqrt{2})^n+B(1-\sqrt{2})^n$$ for some constants $A$ and $B$.

Using the initial conditions $a_0 = 1$ and $a_1 = 3$, you get $$1 = a_0 = A+B$$ $$3 = a_1 = (1+\sqrt{2})A+(1-\sqrt{2})B$$ You simply need to solve this system of equations for $A$ and $B$.

In general, if the characteristic polynomial has distinct roots $r_1, r_2, \cdots, r_k$ each with multiplicity $1$, then the general term will be $a_n = C_1r_1^n+C_2r_2^n+\cdots+C_kr_k^n$.

If the roots $r_1,\ldots,r_n$ have multiplicities $m_1,\ldots,m_k$, then the formula is a bit more complicated: $a_n = p_1(n)r_1^n+\cdots+p_k(n)r_k^n$ where $p_i(n)$ is a polynomial with degree $\le m_i-1$.

JimmyK4542
  • 54,331