2

A friend of mine gave me a math problem whose answer turned out to be

$$f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$$

for some fixed $p$.

I'm trying to find a closed-form solution to the recurrence, if this is possible... but no matter what I try to do (e.g. computing $f(n) - f(n - 1)$, computing $f'(n)$, etc.) I don't get anywhere.

How would I solve this recurrence relation?

user541686
  • 13,772
  • 1
    Recurrence relations don't always have nice solutions. A famous example is the logistic map. You might be lucky though, I don't know. – Ben Millwood Sep 02 '13 at 00:17
  • You might try some numerical experiments and plots to see if the sequence looks familiar. Perhaps some special values of $p$ might help. Usually you settle for some asymptotics instead of closed form solutions. – Maesumi Sep 02 '13 at 00:29
  • 1
    One obvious solution would be $f(n)=0$ for all $n$. Are you looking for all solutions? In that case it would be good to know what the domain and codomain of $f$ are. And are there any assumptions on $f$ other than satisfying this functional equation? Is $f$ differentiable? – Servaes Nov 01 '18 at 12:07
  • For $p=0$ another solution would be $f(n)=1-x^{2^n}$. – Servaes Nov 01 '18 at 12:13

0 Answers0