Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a recurrence relation defined as:


Wolfram Alpha shows that the closed form for this relation is:

$$ f(k)=\exp{(c_2k+c_1)} $$

I'm not really sure how to go about finding this solution (it's been a few years...). Hints?

share|cite|improve this question
up vote 5 down vote accepted

Your recurrence relation can be rewritten to $$\frac{f(k)}{f(k-1)} = \frac{f(k-1)}{f(k-2)}.$$ If we define $g(k)=\frac{f(k)}{f(k-1)}$, this becomes $g(k)=g(k-1)$. Obviously, this implies $g(k)=a$. By definition of $g$ we now have the remaining equation $\frac{f(k)}{f(k-1)} = a$ or $f(k) = af(k-1)$. This is solved by $f(k) = b\cdot a^k$.

To get Wolfram Alpha's version of the solution, we just pick $c_2=\log(a)$ and $c_1=\log(b)$.

share|cite|improve this answer
I think this is the best solution. +1 – Kortlek Jun 13 '13 at 6:32
Beautiful solution and very clear. Thank you for the great explanation! :) – Taj Morton Jun 13 '13 at 7:16

Taking the natural log to both sides, we have

$$ f(k)=\frac{(f(k-1))^2}{f(k-2)}\implies \ln(f(k))=2\ln(f(k-1))-\ln(f(k-2)). $$

Now, let $h(k)=\ln(f(k))$ which transforms our recurrence to the homogeneous recurrence relation

$$ h(k)=2 h(k-1)-h(k-2), $$

which is easy to solve. Now, just solve it for $h(k)$ and subs back in terms of $f(k)$.

share|cite|improve this answer

Asuming for the moment that all $f(n)$ are positive, we can let $g(n)=\ln f(n)$ and obtain the recursion $$\tag1 g(n)=2g(n-1)-g(n-2).$$ The solution space is twodimensional (in other words, $g$ is uniquely determined by $g(0)$ and $g(1)$) and if we try $g(n)=\lambda^n$ as ansatz, we get $\lambda^n=2\lambda^{n-1}-\lambda^{n-2}$, i.e. $$ \lambda^2=2\lambda-1.$$ Normally, the two roots of this quadratic would give us two independant soluitons, henc ea basis for the solution space. Here, we have $\lambda=1$ as double root. In such cases, the second independant solution can be found by taking $g(n)=n\lambda ^n$. (This is not all just taken from thin air, it has to do with eigenvalues of matrices and their normal forms). Therefore the general solution for $(1)$ is obtained by linear-combining the two base solutions found: $g(n)=an+b$ with $a,b\in\mathbb R$. This leads to $f(n)=e^{an+b}$. Beware that we startet with assuming $f(n)>0$ for all $n$ (the exponential does not take negative values or zero). We clearly need that $f(n)\ne 0$ for all $n$ as each $f(n)$ occurs in the denominator sometimes, but we cannot exclude negatives a priori. If we rewrite $f(n)=e^{an+b}=(e^a)^n\cdot e^b=\alpha^n\cdot \beta$ with $\alpha=e^a$, $\beta=e^b$ and note that the restrictions $\alpha>0$, $\beta>0$ are not required. Thus for example $f(n)=7\cdot (-2)^n$ or $f(n)=-7\cdot (-2)^n$ is a solution as well. This would also be covered by allowing complex instead of only real values for $g$ (and $f$), but then one has to be careful as then the absolute value ocurring in the recursion must be taken into account. To do so, we can start over again by lettiung explicitly $g(n)=\ln|f(n)|$, so $g(n)$ is clearly real while still fulfilling $(1)$. Thus again we get $f(n)=an+b$ with $a,b\in\mathbb R$ and at least $|f(n)|=\alpha^n\cdot \beta$ with $\alpha,\beta>0$. Then letting $u_n=\frac{f(n)}{|f(n)|}$, we obtain the recursion $$u_k=\frac1{u_{k-2}}$$ (and hence $u_k=u_{k-4}$) from which we get the general complex solution $$f(n)=u_{n\bmod 4}\cdot \beta\cdot\alpha^n $$ where $\alpha>0$, $\beta>0$, $u_0,u_1\in S^1$, $u_2=\overline{u_0}$, $u_3=\overline{u_2}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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