# What is the nonrecursive formula for the following implicit function?

Given $f(0) = 1-c$, what is the non-recursive $f(n)$ that satify the following equation $f(n)-\frac{1}{2}f(n-1)f(n)+f(n-1) = 1$

for n = 1,2,3,...?

-
Did you try just working out what happens for n=1,2,3,... until you find a pattern? – Reid Barton Apr 14 '10 at 20:47
f(n) is a fractional linear transformation of f(n-1). Composition of fractional linear transformations is essentially the same thing as matrix multiplication, so you can figure out closed forms by computing eigenvectors and eigenvalues. – Qiaochu Yuan Apr 14 '10 at 21:20
@QY: And f(n-1) is the same fractional linear transformation of f(n) :) – Reid Barton Apr 14 '10 at 21:28
Which is essentially what Maple did to solve that. It's nice when mathematical knowledge is so well understood it can be fully automated! It frees humans to do the real creative thinking. – Jacques Carette Apr 14 '10 at 21:34
Random sidenote regarding the Maple comment: Mathematica can find vertical asymptotes logically. You can basically say "solve for x: exists M > 0, exists delta > 0, for all y with |x-y|<delta, f(x) > M" and it will output the values of x where f(x) has positive vertical asymptote. I thought this was pretty cool. – Peter Samuelson Apr 14 '10 at 22:22

$$f(n) = 2{\frac {1-c+ \left( -1 \right) ^{n}-c \left( -1 \right) ^{n}-\sqrt {2}c+ \left( -1 \right) ^{n}\sqrt {2}c}{2-\sqrt {2}-\sqrt {2}c+2 \left( -1 \right) ^{n}+ \left( -1 \right) ^{n}\sqrt {2}+ \left( -1 \right) ^{n}\sqrt {2}c}}$$

which is a non-trivial pattern to spot! [I used a CAS] The thing to notice is that one can transform this first-order recurrence to the constant coefficient 2nd order linear recurrence $$a(n+2)-2a(n) = 0, a(0) = 1, a(1) = -1-c$$ and then transform back. This can be done as the equation is of Riccati type.

I guess I 'cheated' in that I traced through the CAS's process of solving to extract the above information from it. Though if you don't know what you're looking for, it can be rather difficult information to extract...

-
Wow! Not tested yet but it looks like this is it. Thank you so much. – silvanmx Apr 15 '10 at 21:11
What is CAS by the way? – silvanmx Apr 15 '10 at 21:12
CAS = Computer Algebra System. – Jacques Carette Apr 15 '10 at 23:57

We can rewrite the given recurrence as $(f(n) - 2)(f(n-1) - 2) = 2$. That makes it clear that the sequence is 2-periodic.

-
This answer seems to make a mockery of all the other comments! (other than Reid, who seems to be the only other person who spotted this). +1. – Kevin Buzzard Apr 15 '10 at 7:46