MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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,...?

share|cite|improve this question
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
up vote 6 down vote accepted

$$ 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...

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.