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

Question

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

Answer 1

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$.

Answer 2

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.)