3

I have been trying to find the closed-form solution for:

$$T(n) = \dfrac{1}{2}\left(T(n-1)+\dfrac{1}{T(n-1)}\right)$$

I wasn't getting anywhere, so I tried WolframAlpha, which gave me:

$$T(n) = -i\cot(k2^n)$$

For some $k$. So far so good. With a bit of manipulation, I ended up getting an answer:

$$T(n) = \dfrac{\left(\dfrac{T(0)+1}{T(0)-1}\right)^{2^n}+1}{\left(\dfrac{T(0)+1}{T(0)-1}\right)^{2^n}-1} $$

This appears to be correct. So, for all intents and purposes, I have my solution. I could probably work out a proof by "guessing" the formula and showing by induction that it fits the recurrence relation. But I find this method to be rather unsatisfactory. I'm looking for a direct way to derive the 2nd step.

I am somewhat familiar with the most basic homogeneous linear recurrences, so I can intuitively sort of see where the $\cot$ would pop from -- but none of the techniques I'm coming up with quite work. Any suggestions? Thank you.

tohoho
  • 153

1 Answers1

4

Since we have that $$T(n)\pm 1=\frac{(T(n-1))^2\pm 2T(n-1)+1}{2T(n-1)}=\frac{(T(n-1)\pm 1)^2}{2T(n-1)}$$ we obtain $$\frac{T(n)+1}{T(n)-1}=\left(\frac{T(n-1)+1}{T(n-1)-1}\right)^2$$ Now setting $$U(n)=\frac{T(n)+1}{T(n)-1}$$ gives $$U(n)=(U(n-1))^2$$ Taking the logarithm, $$\log U(n)=2\log U(n-1)$$ Setting $V(n)=\log U(n)$ gives $$V(n)=2V(n-1)$$ to have $$V(n)=2^n\cdot V(0)$$ from which we get the closed-form solution you wrote.

mathlove
  • 139,939