1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – plop
    Oct 16 '20 at 16:14
  • $\begingroup$ I am getting 0=c1+c2 and 1=c1+c2.I cant seem to solve this equation.. $\endgroup$
    – jelli
    Oct 16 '20 at 16:24
  • $\begingroup$ 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$. $\endgroup$
    – plop
    Oct 16 '20 at 16:34
  • $\begingroup$ oh I get it ..I am getting O(n) now. $\endgroup$
    – jelli
    Oct 16 '20 at 16:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – plop
    Oct 16 '20 at 16:47
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.