# Find inverse for the closed-form expression of linear recurrence relation

I am trying to find an inverse of the following formula:

$$a_n=\frac{2+\sqrt{6}}{4}(1+\sqrt{6})^n+\frac{2-\sqrt{6}}{4}(1-\sqrt{6})^n$$ This formula is a closed-form expression of a linear recurrence relation and I'd like to find a closed-form expression for the inverse in order to test whether and where (index) a given number occurs in the linear recurrence relation.

I do not know whether this is at all possible (if not, why not?), but a similar problem for the linear recurrence relation describing the Fibonacci numbers has been solved:

\begin{align} F_n&=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(\frac{1-\sqrt{5}}{2})^n\\ &=\frac{\varphi^n-(-\varphi)^{-n}}{\varphi+\varphi^{-1}} = \frac{\varphi^n- (-\varphi)^{-n}}{\sqrt{5}}\\ \text{where } \varphi &= \frac{1 + \sqrt{5}}{2}\\ \text{and }n&=\log_\varphi(\frac{F_n\sqrt{5}+\sqrt{5F_n^2\pm4}}{2}) \end{align}

If it is possible to find an inverse for the mentioned formula, I'm interested in a more general method for approaching the problem, in particular how to manipulate the form: $$c_0(a+\sqrt{b})^n+c_1(a-\sqrt{b})^n$$

Is this form a special form (is it named and/or does it have special properties)? I tried searching for it using terms like "sum of conjugate binomial powers" but failed finding anything that describes this form.

• Have you tried to follow the steps of the Fibonacci case? I don't see anything particular about the number $1,2$ or $5$ in there. – Patrick Da Silva Aug 18 '13 at 21:24
• Is your question given $a_n$ how do you find $n$? Or whether given $a$ you can tell whether it is equal to some $a_n$? This second question looks more difficult to me than with the Fibonacci sequence because $|1-\sqrt 6|\gt 1$ whereas $|\phi^{-1}|\lt 1$ – Mark Bennet Aug 18 '13 at 21:27
• @PatrickDaSilva The Fibonacci formula works by applying the quadratic formula to the equation $\phi^{2n}-F_n\sqrt5 \phi^n\pm 1=0$ to find $\phi^n$ and then take the log to base $\phi$. Here we have $\alpha = 1+\sqrt6$ and $\beta = 1-\sqrt6$ which are not reciprocals of each other, so we don't get a quadratic in the same way. Note that $\alpha \beta =-5$ so if we try to use this approach we get a factor of $(-5)^n$ to deal with somehow. It was $(-1)^n$ for Fibonacci. – Mark Bennet Aug 18 '13 at 21:44
• @BertRegelink - I think you need a $(-\phi)^{-n}$ in one of your formulae – Mark Bennet Aug 18 '13 at 21:50
• @BertRegelink I think that an algorithm would just do fine, since your expression has an exponential growth, it takes a logarithmic amount of operations to find $n$ such that $$a_{n-1} \le x\le a_{n}$$ – chubakueno Aug 18 '13 at 22:26

## 3 Answers

Write this as $a_n = c p^n + d q^n$, where $-p < q < -1$. Now for $n$ sufficiently large we have $|d q^n| < |c| (p^{1/2} - 1) p^n$ and $|d q^n| < |c| (1 - p^{-1/2}) p^n$, so $c p^{n - 1/2} < a_n < c p^{n+1/2}$. Thus, with a finite number of exceptions, if a positive integer $x = a_n$, $n$ will be the nearest integer to $\dfrac{\log x - \log c}{\log p}$. In this case both $\left|\dfrac{d}{|c| (\sqrt{p}-1)} \right|$ and $\left|\dfrac{d}{|c|(1 - 1/\sqrt{p})}\right|$ are less than $1$, so it is true for all nonnegative integers $n$.

• Can you please elaborate about your first inequalities? – chubakueno Aug 19 '13 at 0:48
• I do understand that $a_n =cp^n+dq^n \approx cp^n$ if $|q|<|p|$, just that I didn't understand your proof about why it holds for every nonnegative integer $n$. A thing that may be helpful is that $$\frac{\log(x)-\log(c)}{\log(p)}=\frac{\log(x/c)}{\log(p)}=\log_p(x/c)$$ Just to cut off some calculations. – chubakueno Aug 19 '13 at 1:26
• $|dq^n| < |c| (p^{1/2} - 1) p^n$ if $\left|\dfrac{p}{q}\right|^n > \left | \dfrac{d}{c(p^{1/2} - 1)}\right|$. In particular it's true for all $n \ge 0$ if $p > |q|$ and the right side $< 1$. – Robert Israel Aug 19 '13 at 4:23

EDIT : Dah, doesn't work as the first commentor pointed out. I guess I had to write it all out to see where it failed! I leave the answer there for the curious.

The quadratic approach works, it just requires some good thinking (at least in this case it works!).

So you begin with $$a_n = \frac{2+\sqrt 6}4 \left( 1 + \sqrt 6 \right)^n + \frac{2-\sqrt 6}4 \left( 1 - \sqrt 6 \right)^n.$$ I decided to write $\varphi_6 \overset{def}= 1 + \sqrt 6$ and $\overline{\varphi}_6 \overset{def}= 1 - \sqrt 6$, so that the above equation can be re-written as $$4 a_n = (1 + \varphi_6) \varphi_6^n + (1+\overline{\varphi}_6)\overline{\varphi}_6^n.$$ Note that $\varphi_6 \overline{\varphi}_6 = -5$, hence $$4 a_n \varphi_6^n = (1+\varphi_6)\varphi_6^{2n} + (1+\overline{\varphi}_6)(-5)^n.$$ The quadratic equation $$(1+\varphi_6) y^2 - 4a_n y + (-5)^n(1+\overline{\varphi}_6) = 0$$ has the solution $\varphi_6^n$, hence by noticing that $$(1+\varphi_6)(1+\overline{\varphi}_6) = (2+\sqrt 6)(2-\sqrt 6) = -2,$$ we obtain $$\varphi_6^n = \frac{4a_n \pm \sqrt{ 16a_n^2 -4(1+\varphi_6)(1+\overline{\varphi}_6)(-5)^n } }{2(1 + \varphi_6)} = \frac{4a_n \pm \sqrt{ 16a_n^2 + 8(-5)^n } }{2(1 + \varphi_6)} ;$$ but we need to determine this sign, as we only know $\varphi_6^n$ belongs to one of the two possible signs. If $n$ is even, then $$4a_n = \sqrt{16a_n^2} < \sqrt{16 a_n^2 + 8 (-5)^n},$$ hence since $\varphi_6 > 0$, we must take the $+$ sign. If $n$ is odd, denote by $\psi_n$ the other root of the quadratic that $\varphi_6^n$ solves. Then for a quadratic with given coefficients $a,b,c$ and roots $r_1, r_2$, we see that $$ay^2 + by + c = a(y^2 + \frac ba y + \frac ca) = a (y - r_1)(y - r_2) = a(y^2 - (r_1+r_2)y + r_1 r_2) \quad \Longrightarrow \quad r_1 r_2 = \frac ca.$$ Using this identity with the approximations $\varphi_6 \approx 3.45$ and $\frac 5{\varphi_6} \approx 1.45$, we can see that $$\varphi_6^n \psi_n = \frac{1+\overline{\varphi}_6}{1+\varphi_6} (-5)^n = 5^n \frac{-(1+\overline{\varphi}_6)}{1+\varphi_6} \approx 5^n \cdot 0.1 \quad \Longrightarrow \quad \psi_n \approx \frac{(1.45)^n}{10} < (3.45)^n = \varphi_6^n,$$ so that $\varphi_6^n$ corresponds again to the $+$ sign since the two roots are $\varphi_6^n$ and $\psi_n$ but $\varphi_6^n > \psi_n$.

(Note that the discriminant of the quadratic for $\varphi_6^n$ must be positive since $\varphi_6$ is a real number ; in other words, $a_n^2 > \frac{5^n}2$ for $n$ odd, we don't have to make the check.)

So we have $$\varphi_6^n = \frac{4a_n + \sqrt{ 16a_n^2 + 8(-5)^n } }{2(1 + \varphi_6)},$$ hence $$n = \frac{ \log \left( \frac{4a_n + \overset{\, \, \, \quad \qquad \displaystyle{\downarrow}}{\sqrt{ 16a_n^2 + 8(-5)^n } }}{2(1 + \varphi_6)} \right) }{\log(\varphi_6)}.$$ (Arrow points to why it failed.)

Hope that helps,

• In your last equation, you haven't elimined $n$, and you can factor the $2$ and simplify in the upper logarithm – chubakueno Aug 18 '13 at 22:58
• @chubakueno : Dear god, how could I forget that one! ... Damn it. – Patrick Da Silva Aug 18 '13 at 22:59
• I think the last equation thay Bert Regelink proposes is not exactly solvable, just that in fibonacci you have reciprocals And finally, off-topic, but at the same time not. – chubakueno Aug 18 '13 at 23:04
• @chubakueno : Factoring the $2$ out at this point is irrelevant because it won't lead to getting rid of $n$. – Patrick Da Silva Aug 18 '13 at 23:09

What I would do:

$$\log(a r^n+b s^ n)= n\log r + \log (a+ b t^n)\sim n\log r + \log a$$

if $t=s/r$ has $|t|<1$. Everything is monotonic (up to a period of 2) so it's easy to precalculate early terms and then, for larger (in a rigorously defined way) terms, take $n_0$ to be the estimate of $n$ from inverting the above, then check nearby $n$ ($\pm1$ say) to verify if one has a match.