# Closed Form of Recurrence Relation

I have a recurrence relation defined as:

$$f(k)=\frac{[f(k-1)]^2}{f(k-2)}$$

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?

-

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

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

-

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

-