1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Did you try just working out what happens for n=1,2,3,... until you find a pattern? $\endgroup$ Apr 14, 2010 at 20:47
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 14, 2010 at 21:20
  • 2
    $\begingroup$ @QY: And f(n-1) is the same fractional linear transformation of f(n) :) $\endgroup$ Apr 14, 2010 at 21:28
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 14, 2010 at 21:34
  • $\begingroup$ 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. $\endgroup$ Apr 14, 2010 at 22:22

2 Answers 2

6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Wow! Not tested yet but it looks like this is it. Thank you so much. $\endgroup$
    – silvanmx
    Apr 15, 2010 at 21:11
  • $\begingroup$ What is CAS by the way? $\endgroup$
    – silvanmx
    Apr 15, 2010 at 21:12
  • $\begingroup$ CAS = Computer Algebra System. $\endgroup$ Apr 15, 2010 at 23:57
14
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Apr 15, 2010 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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