What is this function related with continued fractions?
What is this function related with continued fractions?
Playing with continued fractions, I came with the idea of iterating the limit of the simplest one:
$$1 + cfrac11+cfrac11+cfrac11+cfrac11+cfrac11+cdots = Phi$$
And then I thoght about iterating the result:
$$Phi + cfrac1Phi+cfrac1Phi+cfrac1Phi+cfrac1Phi+cfrac1Phi+cdots = ?$$
And after that keep iterating again and again. Essentially, what I am doing is solving this:
$$x = a + frac1x$$
for different values of $a$. Whose solution is:
$$ x = fraca pm sqrta^2 + 42$$
And I'm just staying with the positive solution. At the end, I'm just exploring this sequence defined recursively:
$$ f(1) = Phi \
f(n+1) = fracf(n) + sqrtf(n)^2 + 42
$$
When you see the plot of the terms of the sequence, you get this picture:
I would like to know which is the function that generates that curve. It really seems to be a continuos function (notice that the picture is a set of points so close, that may seem to be continuous, but it's not).
So... What's the function underlying this curve and how can we find it?
Many thanks in advance!
$begingroup$
The recursion can be written like $$ f(n+1) - f(n) = fracsqrtf(n)^2 + 4 - f(n)2 = frac2sqrtf(n)^2 + 4 + f(n)$$ If one at this stage removes the 4 in the denominator and solves a continuous approximation $ f' = frac1f$ i.e. $(f^2)' = 2$, we end up with a square root shape, which roughly agrees with the graph wolframalpha.com/input/?i=plot+2sqrt(x)+from+0+to+5000
$endgroup$
– Calvin Khor
Sep 12 '18 at 11:47
$begingroup$
I certainly can't (haven't) prove this, but it looks like something of the form $asqrtbx$ for constants $a$ and $b$.
$endgroup$
– YiFan
Sep 12 '18 at 11:54
$begingroup$
The next correction after Calvin's formula is $f'=frac1f-frac1f^3$ which gives $2n=f^2+log*(f^2-1)$
$endgroup$
– Empy2
Sep 12 '18 at 12:19
$begingroup$
... or $f(n)=sqrt2n-ln(2n)$
$endgroup$
– Empy2
Sep 12 '18 at 12:27
4 Answers
4
Using what has been given in comments.
If we use $$2n=f^2+log(f^2-1)implies 2n-1=(f^2-1)+log(f^2 -1)$$ let $t=(f^2-1)$ to make
$$2n-1=t+log(t)implies t, e^t=e^2n-1implies t=Wleft(e^2 n-1right)$$ where appears Lambert function making the final solution to be
$$f=sqrt1+Wleft(e^2 n-1right)tag1$$
If we use
$$n=frac14 f left(f+sqrtf^2+4right)+sinh ^-1left(fracf2right)$$ and expand the rhs as a series for infinitely large values of $f$, we should get
$$n=fracf^22+frac12+log left(fright)+Oleft(frac1f^2right)=fracf^22+frac12+frac12log left(f^2right)+Oleft(frac1f^2right)$$ and, ignoring the higher order terms, the same process would lead to
$$f=sqrtWleft(e^2 n-1right)tag2$$
Now, for large values of $n$, you could use the asymptotic series given in the linked Wikipedia page
$$W(x)=L_1-L_2+fracL_2L_1+fracL_2(L_2-2)2L_1^2+fracL_2(6-9L_2+2L_2^2)6L_1^3+cdots$$ where $L_1=log(x)$ and $L_2=log(L_1)$ and get, as a very first approximation
$$fapprox sqrt(2n-1)-log(2n-1)$$
To allow you to compare with your numbers, I generated a table of numerical values
$$left(
beginarraycc
n & (1) \
500 & 31.5135 \
1000 & 44.6363 \
1500 & 54.6991 \
2000 & 63.1800 \
2500 & 70.6504 \
3000 & 77.4035 \
3500 & 83.6131 \
4000 & 89.3925 \
4500 & 94.8203 \
5000 & 99.9539
endarray
right)$$
$begingroup$
A little problem with your equation (1). It does not satisfy the defining recursion $f(n+1) =(f(n) + sqrtf(n)^2 + 4)/2$ and thus it is not clear to me how this relates to $f(n)$ in the question..
$endgroup$
– Somos
Sep 13 '18 at 17:02
$begingroup$
@Somos. As I wrote at the start of my answer, I just took what had already be written in comments. No more ! For sure, neither $(1)$ or $(2)$ satisfy the defining recursion but they seem to be quite close to.
$endgroup$
– Claude Leibovici
Sep 14 '18 at 2:11
This question is similar to MSE question 1072256 "$a_n+1 = log(1+a_n), a_1>0.$ ..." and to MSE question 3215 "Convergence of $sqrtnx_n$ where $x_n+1=sin(x_n)$". Because of the similarities, it is natural to assume that there is a power series
$, f(n) approx f^*(n) := sqrt2n ,
(1 + c_1 x - c_2 x^2 + c_3 x^3 - c_4 x^4 + O(x^5)) ,$ where $, x := 1/n ,$ and
$, c_k ,$ is a polynomial of degree $k$ in $, y := log(x). ,$ Using the defining recursion for $, f(n) ,$ we can solve for the coefficients $, c_k ,$ to get
$$ c_1 = c + y/8, quad c_2 = (1+4c)^2/32 + (1+4c)y/32 + y^2/128,$$ $$ c_3 !=! frac11 !+! 120 c !+! 384 c^2 !+! 384 c^3768 !+! frac5 !+! 32 c !+! 48 c^2256 y !+!
frac1 !+! 3 c128 y^2 !+! fracy^31024,$$
where $, c,$ is a constant depending on $, f(0). ,$ If we use the initial values
$, f(0) = 0, f(1) = 1, , f(2) = phi, dots, ,$
then $, c approx -0.291131527. ,$
Note that since $, sqrt1/2-1 approx -0.292 ,$ the formula is already close for $, n=1.$
To judge the accuracy, we get
$, f(1) = 1, ,$ $ f^*(1) approx 1.00269, ,$
$f(2) approx 1.61803, ,$ $ f^*(2) approx 1.61826, ,$
$f(3) approx 2.09529, ,$ and $ f^*(3) approx 2.09535. ,$
I think you can set up a differential equation and solve it.
begineqnarray
2f'(n) &= -f(n)+sqrtf(n)^2+4\
textdn&=frac2, textd! f-f+sqrtf^2+4 \
n &= frac14 (f (f + sqrt4 + f^2 + 4 sinh^-1left(fracf2right)
endeqnarray
Solving for $f$ should result in the function you wanted.
Wolfram plot
$begingroup$
Wouldn't this just be an approximation, because $f'(n) sim f(n+1) - f(n)$ but it is not equal unless $f$ is linear.
$endgroup$
– Dark Malthorp
Sep 12 '18 at 15:31
$begingroup$
I think you can define a discrete derivative this way, no need for $f$ to have the property of linearity.
$endgroup$
– Michael Paris
Sep 12 '18 at 15:35
$begingroup$
right but then you would have to do a discrete integral (i.e. a summation) instead of a continuous integral.
$endgroup$
– Dark Malthorp
Sep 12 '18 at 15:37
$begingroup$
I thought this would suffice as an approximation, but now I think you are correct. If I do not think of a good reason, I will delete the answer after some time
$endgroup$
– Michael Paris
Sep 12 '18 at 15:47
One way to solve this is to use the theory of continuous iterations, which is often best tackled using power series around fixed points. Let $g(z) = fracz + sqrtz^2 + 42$. Then notice
$$
g^-1(w) = fracw^2 - 1w
$$
This has no fixed points except at infinity, but we can actually make use of that if we conjugate by $wto frac1w$, since $h(w) = frac1g^-1(1/w)$ will have a fixed point at $w=0$. We can see the series for $h(w)$ is given by $$
h(w) = fracw1-w^2 = w + w^3 + w^5 + ...
$$
Formally composing this series with itself is fairly straightforward, for example:
begineqnarray
h(h(w)) &=& (w + w^3 + w^5 +...) + (w + w^3 + w^5 +...)^3 + (w + w^3 + w^5 +...)^5 + ...
\ &=& w + 2w^3 + 2w^5 + ...
endeqnarray
In general, we will have
$$
h^n(x) = w + p_3(n)w^3 + p_5(n)w^5 + ...
$$
where $p_i(n)$ satisfy a recurrence given by
beginequation
w + p_3(n+1) w^3 + p_5(n+1)w^5 + ... = h^n+1(x) = h(h^n(x)) \ = (w + p_3(n)w^3 + p_5(n)w^5 + ...) + (w + p_3(n)w^3 + p_5(n)w^5 + ...)^3 + (w + p_3(n)w^3 + p_5(n)w^5 + ...)^5 + ... \ = w + (p_3(n) + 1) w^3 + (p_5(n) + 3p_3(n) + 1) w^5 + ...
endequation
We get recursions like $p_3(n+1) = p_3(n) + 1$. Clearly, this is solved by $p_3(n) = n$. The $w^5$ coefficient is $p_5(n+1) = p_5(n) + 3n + 1$, which is solved by $p_5(n) = n + frac32 n(n+1)$. In general, you can actually find a unique polynomial for each $p_i(n)$ by using Faulhaber's formula since each one is defined by a recursion $p_i(n+1) = p_i(n) + q_i(n)$ for some appropriate polynomial $q_i(n)$. Notice this recursion will still be satisfied for noninteger $n$, so we have a function $H(t,w) = w + p_3(t)w^3 + p_5(t)w^5 +...$ satisfying:
$$
H(t+1,w) = h(H(t,w))
$$
OK so what does this have to do with the original question? Well, we have
begineqnarray
H(t+1,w) &=& frac1g^-1(1/H(t,w)) \
frac1H(t+1,w) &=& g^-1left(frac1H(t,w)right) \
gleft(frac1H(t+1,w)right) &=& frac1H(t,w)
endeqnarray
substituting $-n = t+1$, and recalling the definition of $g$, we find:
begineqnarray
frac1H(-(n+1),w) &=& gleft(frac1H(-n,w)right) \
frac1H(-(n+1),w) &=& fracfrac1H(-n,w) + sqrtfrac1H(-n,w)^2 + 42
endeqnarray
Then, as you can see, we will have $f(n) = frac1H(-n,w)$, where $w$ is the starting value. I do not expect this function to have a nice closed form.
This formula for $f$ is only helpful on a small scale, but it does demonstrate we can draw a smooth (hence continuous) function through those points. If you want to know about the asymptotic behavior of $f(n)$ as $ntoinfty$, somos has already covered that in his answer.
$begingroup$
What you describe won't really solve the problem. That is, you won't get the correct behavior $, f(n) sim sqrt2n.$ In particular this approach won't give the logarithms in the series expansion.
$endgroup$
– Somos
Sep 12 '18 at 16:23
$begingroup$
Yea I guess it doesn't give any information about the asymptotics of $f$.
$endgroup$
– Dark Malthorp
Sep 12 '18 at 16:28
$begingroup$
The main thing this solution gives is a smooth interpolation that still satisfies the recursion
$endgroup$
– Dark Malthorp
Sep 12 '18 at 16:31
$begingroup$
Yes, it does, but only locally. I have used similar methods myself for this kind of problem, but I know it has severe limitations. It is similar to polynomial interpolation. It doesn't work well for extrapolation.
$endgroup$
– Somos
Sep 12 '18 at 16:36
$begingroup$
Definitely a valid point! Of course, given $f$ locally you can use the recursion to extend it, but you need an asymptotic expansion to know what that will look like. I don't really have anything to contribute with regards to asymptotics, I think you covered that in your answer perfectly well.
$endgroup$
– Dark Malthorp
Sep 12 '18 at 16:49
Thanks for contributing an answer to Mathematics Stack Exchange!
But avoid …
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Required, but never shown
Required, but never shown
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
$begingroup$
When $a=1$, then it converges to the golden-ratio, when $a=2$ it converges to the silver-ratio (en.wikipedia.org/wiki/Silver_ratio) And more generaly for $a=n$ it converges to the $n$'th metalic number. I would be very tempted to say that this always converges for $a>0$ to $fraca+sqrta^2+42$ as in en.wikipedia.org/wiki/Metallic_mean.
$endgroup$
– P. Quinton
Sep 12 '18 at 11:30