2

How can I express a closed-form formula for the following equation? $$f(n)=f(n-1)+\frac{C}{f(n-1)} $$ Where $C>0$ and $f(0)=\sqrt{C}$.

user3563894
  • 221
  • What is the source of this problem? – lulu Jan 06 '20 at 18:38
  • An equation I encounter during my research. – user3563894 Jan 06 '20 at 18:39
  • Have you tried working out the first few terms? – JonathanZ Jan 06 '20 at 18:39
  • Yep. still I did not observed any behavior of the results – user3563894 Jan 06 '20 at 18:40
  • @user3563894 If it helps, $f_n$ is increasing and divergent. – PierreCarre Jan 06 '20 at 18:46
  • You can show that $f()$ will always be of the form $g(n)\sqrt{C}$, and that $g(n)$ satisfies the recurrence $g(n)=g(n-1)+1/(g(n-1))$. This sequence has been studied pretty extensively, I believe. I don't think an explicit form is known, but the asymptotics are known (this shows up in Spivak's Companion to Concrete Mathematics IIRC). – Steven Stadnicki Jan 06 '20 at 18:46
  • I know. But I need the exact formula – user3563894 Jan 06 '20 at 18:56
  • There almost certainly is not an exact formula. – Steven Stadnicki Jan 06 '20 at 18:59
  • Actually, I take that back - given the nature of the recurrence (if $g(n)=a(n)/b(n)$ then $a(n+1)=a(n)^2+b(n)^2$ and $b(n+1)=a(n)b(n)$, and it's not too hard to show inductively that $GCD(a(n),b(n))=1$ for all $n$) there may be an explicit constant $C$ such that $b(n)=\lfloor C^{2^n}\rfloor$ or some very similar formula — but computing such a C is likely no easier than computing the sequence itself. – Steven Stadnicki Jan 06 '20 at 19:03
  • More to the point, given the comment above, the numerator and denominator in the 'exact formula' for $g()$ grow super-exponentially, so they're likely to be beyond reasonable computational limits in very short order; why do you need the exact formula? – Steven Stadnicki Jan 06 '20 at 19:07
  • Maybe there is a way to represent the formula as $g(n)=a^n/b^n$? – user3563894 Jan 06 '20 at 19:12
  • @user3563894 It can't be that simple; the asymptotics on the formula you give would either be $g(n)\to 1$ or $g(n)\gt c^n$ for some $c\gt 1$, but it doesn't grow that fast. What's more, the terms of the numerator and denominator must grow super-exponentially (I can go into detail on this in an answer, if you want). – Steven Stadnicki Jan 06 '20 at 19:27
  • @PierreCarre The point of my (original) comment was that the question for all $C$ comes down to the question for $C=1$; if $g(n)$ satisfies the recurrence for $C=1$, then $f(n)=g(n)\sqrt{C}$ satisfies it for any given $C$. – Steven Stadnicki Jan 06 '20 at 19:28

2 Answers2

5

Your $f(n) = \sqrt{C} g(n)$, where $g(n)$ is obtained by the recursion $$ g(n) = g(n-1) + 1/g(n-1)$$ with $g(0)=1$. The numerators are OEIS sequence A073833, denominators A073834, and $g(n)$ is the fractional chromatic number of the Mycielski graph $M_{n+1}$. There seems to be no closed-form formula, though.

Robert Israel
  • 448,999
0

This is the best I can do. It seems like \begin{align} \frac{f(n)-f(n-1)}{n-(n-1)} = \frac{C}{f(n-1)}. \end{align} Let us solve the differential equation \begin{align} f' = \frac{C}{f} \ \ \implies \ \ \frac{d}{dx}(f)^2 = C \end{align} which means $f^2 = Cx$ or $f(x) = \sqrt{C}\sqrt{x}$. Observe \begin{align} \sqrt{C}\sqrt{n}-\sqrt{C}\sqrt{n-1} = \frac{\sqrt{C}}{\sqrt{n}+\sqrt{n-1}} \end{align} then it follows \begin{align} \frac{\sqrt{C}}{2f(n)}=\frac{\sqrt{C}}{2\sqrt{n}}\leq f(n)-f(n-1) \leq \frac{\sqrt{C}}{2\sqrt{n-1}} = \frac{\sqrt{C}}{2f(n-1)} \end{align}

Jacky Chong
  • 25,739