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 == 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? 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)}}
RSolve[a[n + 1] == 4 a[n] (1 - a[n]), a[n], n]
{{a[n] -> 1/2 - 1/2 Cos[2^n C]}}

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 = 2;
sol[n_] := -Floor[c^(2^n)]

correct = RecurrenceTable[{a[n + 1] == a[n] (1 - a[n]), a == 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. May 14 '16 at 18:20

Form here you should use: RecurrenceTable

sol = RecurrenceTable[{a[n + 1] == a[n] (1 - a[n]), a == 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. 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 == 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 == 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 = 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; // RepeatedTiming
(* {0.16, Null} *)

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

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

a = 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! ;) May 15 '16 at 2:10