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

Question

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.

Answer 1

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,

Answer 2

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.

Answer 3

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