# Recurrence $f(n+1)=2f(n)-f(n-1)$ with initial values $f(0)=0,f(1)=1$

How do I solve the following recurrence? $$f(0) = 0, \quad f ((1)) = 1, \quad f((n+1)) = 2*f(n) - f(n-1).$$

• For the equation without initial conditions, there are two solutions of the form $f(n)=a^n$ and $f(n)=na^n$ for some value of $a$. Find what $a$ should be. Well, you already found that $a=1$. All solutions to the equation without initial conditions are of the form $f(n)=c_1a^n+c_2na^n$. You can then find the values of $c_1,c_2$ by imposing the initial conditions to be satisfied.
– plop
Oct 16 '20 at 16:14
• I am getting 0=c1+c2 and 1=c1+c2.I cant seem to solve this equation.. Oct 16 '20 at 16:24
• Those are not the equations that you get. The condition $0=f(0)$ gives $0=f(0)=c_1\cdot 1^0+c_2\cdot 0\cdot 1^0=c_1$.
– plop
Oct 16 '20 at 16:34
• oh I get it ..I am getting O(n) now. Oct 16 '20 at 16:41
• Well, you get more than that. You get the exact solution, which is $f(n)=n$. But your instructor(s) are to blame for conflating the ideas of solving a recurrence with that of finding asymptotics of its solutions.
– plop
Oct 16 '20 at 16:47

The normal recipe for solving a recurrence of this form goes like this:

1. Determine the polynomial corresponding to the recurrence, in your case $$x^2 - 2x + 1$$.
2. Determine the roots of the polynomial, in your case $$x = 1$$ (double root).
3. The solution is a linear combination of $$1^n$$ and $$n1^n$$ (more generally, if the roots are $$\lambda_1,\ldots,\lambda_r$$ with multiplicities $$m_1,\ldots,m_r$$, then you get a linear combination of $$\lambda_1,\ldots,n^{m_1-1} \lambda_1,\ldots,\lambda_r,\ldots,n^{m_r-1}\lambda_r$$).
4. Find the coefficients using the initial conditions. In your case, the general solution is $$A + Bn$$. Since $$f(0) = 0$$, we have $$A = 0$$, and since $$f(1) = 1$$, we have $$A + B = 1$$, hence $$B = 1$$. Thus the solution is $$0 + 1 \cdot n = n$$.

Here are two more equivalent ways to solve this.

Matrices. Notice that $$\begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix} = \begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix}.$$ It follows that $$\begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix} = \begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}.$$ The characteristic polynomial of the matrix is $$\det \begin{pmatrix} t-2 & 1 \\ -1 & t \end{pmatrix} = (t-2)t+1 = (t-1)^2,$$ hence there is a single eigenvalue with multiplicity $$2$$. To determine the Jordan form of this matrix, which we denote by $$A$$, notice that $$\begin{pmatrix} 2 & -1 \\ 1 & 0 \end{pmatrix} - I = \begin{pmatrix} 1 & -1 \\ 1 & -1 \end{pmatrix}$$ has rank $$1$$, and so the Jordan form of $$A$$ is $$\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}.$$ The above shows that one eigenvector of $$A$$ is $$v = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$$. A generalized eigenvector of the matrix is a vector $$u$$ such $$(A-I)u = w$$, for example $$u = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$$. It follows that $$\begin{pmatrix} 2 & -1 \\ 1& 0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{-1} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix}.$$ It follows that $$\begin{pmatrix} f(n+1) \\ f(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^n \begin{pmatrix} 0 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} n \\ 1 \end{pmatrix} = \begin{pmatrix} n+1 \\ n \end{pmatrix}.$$ In particular, $$f(n) = n$$.

Generating functions. Let $$P(x) = \sum_{n=0}^\infty f(n) x^n$$. Then \begin{align} P(x) &= x + \sum_{n=2}^\infty f(n) x^n \\&= x + \sum_{n=2}^\infty [2f(n-1)-f(n-2)] x^n \\ &= x + 2x\sum_{n=1}^\infty f(n) x^n - x^2 \sum_{n=0}^\infty f(n) x^n \\ &= x + (2x-x^2) P(x). \end{align} It follows that $$P(x) = \frac{x}{1-2x+x^2} = \frac{x}{(1-x)^2} = x \sum_{n=0}^\infty \binom{n+1}{1} x^n = \sum_{n=0}^\infty n x^n.$$ Therefore $$f(n) = n$$.

Here are some value of the function defined by your recurrence: $$\begin{array}{c|cccccc} n & 0 & 1 & 2 & 3 & 4 & 5 \\\hline f(n) & 0 & 1 & 2 & 3 & 4 & 5 \end{array}$$ Hopefully you can guess the answer, and then prove it by induction.

Morale: calculate the first few values of the recurrence.

(Once you do that, it's always a good idea to check whether the OEIS contains it.)