4
$\begingroup$

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

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

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.

$\endgroup$
  • 1
    $\begingroup$ and even for r = - 2. $\endgroup$ – Mariusz Iwaniuk May 14 '16 at 18:20
3
$\begingroup$

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]

enter image description here

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

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]

Mathematica graphics

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} *)
$\endgroup$
2
$\begingroup$

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]);
$\endgroup$
  • $\begingroup$ n^2 complexity, gah! ;) $\endgroup$ – Lucas May 15 '16 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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