# Solving Recurrence Equation $a_{n+1}=a_n(1-a_n)$

How to solve following recurrence equation

$$a_0=2$$ $$a_{n+1}=a_n(1-a_n)$$

I tried:

sol=RSolve[{a[n + 1] == a[n] (1 - a[n]), a[0] == 2}, a[n], n]

ListPlot[{sol}]


but it doesn't work.

how to find the sequence $a_n$?

• By the way, where did you encounter this recurrence relation? – Chip Hurst May 25 '16 at 0:13

Your recurrence is an instance of the logistic map $$x_{n+1} = r x_n(1 - x_n).$$

The first sentence of the Solution in some cases section in the link above says:

The special case of r = 4 can in fact be solved exactly, as can the case with r = 2; however the general case can only be predicted statistically.

Mathematica is indeed able to solve the $r=2$ and $r=4$ cases:

RSolve[a[n + 1] == 2 a[n] (1 - a[n]), a[n], n]

{{a[n] -> 1/2 - 1/2 E^(2^n C[1])}}

RSolve[a[n + 1] == 4 a[n] (1 - a[n]), a[n], n]

{{a[n] -> 1/2 - 1/2 Cos[2^n C[1]]}}


So I think no one really knows a proper closed form of your nonlinear recurrence.

In fact the wiki link makes it seem like the solution is highly dependent on the initial condition, i.e. a small change in the initial condition will result in a large change in the solution.

## Edit

A quick search on OEIS almost gives us a closed form. A007018 gives the formula

$$a(n) = -\left\lfloor c^{2^n} \right\rfloor,$$

where

$$c = 1.597910218031873178338070118157\ldots$$

Now the issue here is knowing the precise value of $c$. In fact we need to know many decimal places of $c$ to be able to find the first few values of $a(n)$.

A077125 gives the first 105 digits and that's only enough to give us the first $8$ values of $a(n)$:

c = 1.59791021803187317833807011815745531236222495318211419659139309422961619562279496876114706281963518250566;

SetAttributes[sol, Listable];

sol[0] = 2;
sol[n_] := -Floor[c^(2^n)]

correct = RecurrenceTable[{a[n + 1] == a[n] (1 - a[n]), a[0] == 2}, a[n], {n, 0, 10}]];

(* relative error *)
1. - sol[Range[0, 10]]/correct

{0., 0., 0., 0., 0., 0., 0., 0., 0., 5.92121*10^-103, 1.18326*10^-102}


So I guess this is a way to approximate solutions and I imagine that's what the quote from above "can only be predicted statistically" means.

• and even for r = - 2. – Mariusz Iwaniuk May 14 '16 at 18:20

Form here you should use: RecurrenceTable

 sol = RecurrenceTable[{a[n + 1] == a[n] (1 - a[n]), a[0] == 2}, a[n], {n, 0, 6}]


with result:

{2, -2, -6, -42, -1806, -3263442, -10650056950806}

And plot:

ListLogPlot[Abs[sol], Filling -> Bottom]


• I'd have just used NestList[# (1 - #) &, 2, 6] myself. – J. M. will be back soon May 14 '16 at 13:12

I don't know why RSolve is unable to yield a result for

RSolve[{a[n + 1] == a[n] (1 - a[n]), a[0] == 2}, a[n], n]


If we apply a multiplier of 2 it gives an answer

RSolve[{a[n + 1] == 2 a[n] (1 - a[n]), a[0] == 2}, a[n], n]


I would be most interested to understand why the former has no solution using RSolve. Note that removing the boundary condition doesn't result in an answer.

## Fast recursive function

Since RSolve doesn't work we can at least define a function that will give the desired answer.

Below is a copy of one from A.G.'s answer

a[0] = 2;
a[n_] := a[n - 1] (1 - a[n - 1]);


and a faster version that uses Fold.

af[n_Integer /; n > -1] := Fold[# (1 - #) &, 2, Range[n]]


Timing Test

a[16]; // RepeatedTiming
(* {0.16, Null} *)

af[16]; // RepeatedTiming
(* {0.0001, Null} *)


Not the most compact, but you can define recursive functions like this :

a[0] = 2;
a[n_] := a[n - 1] (1 - a[n - 1]);
Table[a[k], {k, 0, 6}]
(* {2, -2, -6, -42, -1806, -3263442, -10650056950806} *)


If you care about speed/efficiency just add memoization to make it run in linear time:

a[n_] := a[n] = a[n - 1] (1 - a[n - 1]);

• n^2 complexity, gah! ;) – Lucas May 15 '16 at 2:10