3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Very nice indeed. $\endgroup$ – Clement C. Dec 28 '16 at 14:51
  • $\begingroup$ Excellent answer, thank you very much. $\endgroup$ – tohoho Dec 28 '16 at 14:59

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.