5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Patrick Da Silva Aug 18 '13 at 21:24
  • 1
    $\begingroup$ 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$ $\endgroup$ – Mark Bennet Aug 18 '13 at 21:27
  • 1
    $\begingroup$ @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. $\endgroup$ – Mark Bennet Aug 18 '13 at 21:44
  • 1
    $\begingroup$ @BertRegelink - I think you need a $(-\phi)^{-n}$ in one of your formulae $\endgroup$ – Mark Bennet Aug 18 '13 at 21:50
  • 2
    $\begingroup$ @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}$$ $\endgroup$ – chubakueno Aug 18 '13 at 22:26
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Can you please elaborate about your first inequalities? $\endgroup$ – chubakueno Aug 19 '13 at 0:48
  • $\begingroup$ 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. $\endgroup$ – chubakueno Aug 19 '13 at 1:26
  • $\begingroup$ $|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$. $\endgroup$ – Robert Israel Aug 19 '13 at 4:23
0
$\begingroup$

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,

$\endgroup$
  • 2
    $\begingroup$ In your last equation, you haven't elimined $n$, and you can factor the $2$ and simplify in the upper logarithm $\endgroup$ – chubakueno Aug 18 '13 at 22:58
  • $\begingroup$ @chubakueno : Dear god, how could I forget that one! ... Damn it. $\endgroup$ – Patrick Da Silva Aug 18 '13 at 22:59
  • 1
    $\begingroup$ 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. $\endgroup$ – chubakueno Aug 18 '13 at 23:04
  • $\begingroup$ @chubakueno : Factoring the $2$ out at this point is irrelevant because it won't lead to getting rid of $n$. $\endgroup$ – Patrick Da Silva Aug 18 '13 at 23:09
0
$\begingroup$

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.

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