Recursive Equations

[fog37]

TL;DR Summary

Recursive equations as composite equations

Hello,

I am trying to better understand the following discrete, recursive equation (logistic equation):
$$x_{n+1} =r x_n (1- x_n)$$
Is this an equation with two variables, $x$ and $t$, where $t$ assumes discrete values, or is it an equation with one single variable, the variable $x$? Is it a composite function?

If $n$ is the time integer variable, then the value of the variable $x$ at time $n \Delta t$ seconds depends on the value of $x$ at time $(n-1) \Delta t$. Time is discrete and changes by $\Delta t$.

If time was not discrete but continuous, how would the equation look like? Would it be $x(t)= r x(t-1) [1-x(t-1)]$? I don't think so...

thanks!

 

[Mark44]

Summary:: Recursive equations as composite equations

Hello,

I am trying to better understand the following discrete, recursive equation (logistic equation):

https://www.physicsforums.com/attachments/278845

Is this an equation with two variables, $x$ and $t$, where $t$ assumes discrete values, or is it an equation with one single variable, the variable $x$? Is it a composite function?

If $n$ is the time integer variable, then the value of the variable $x$ at time $n \Delta t$ seconds depends on the value of $x$ at time $(n-1) \Delta t$. Time is discrete and changes by $\Delta t$.

If time was not discrete but continuous, how would the equation look like? Would it be $x(t)= r x(t-1) [1-x(t-1)]$? I don't think so...

thanks!

The equation you wrote doesn't involve t at all. I would say that the equation involves a parameter, r, and a sequence of numbers $\{x_n\}$, where the sequence is defined recursively. Given r and $x_0$ all the numbers in the sequence can be determined.

BTW, it's better to write the equation you wrote in LaTeX than as an image.
$$x_{n+1} = rx_n(1 - x_n)$$

 

[fog37]

Thanks. The equation definitely generates a sequence of values. But the variable $n$ could be consider a time variable so $x_n$ is the value of $x$ at time $t$.

But isn't the equation the discrete version of an equation involving $x$ as a function of $t$ like the equation below where $N(t)$ represents $x(t)$? The continuous logistic equation surely looks different.

 

[Mark44]

Thanks. The equation definitely generates a sequence of values. But the variable n could be consider a time variable so $x_n$ is the value of x at time t.

Not necessarily. A sequence is a function that maps the non-negative integers to the reals. So in a sequence, the difference between two successive indexes is always 1, whereas times don't have to increase 1 second or 1 minute or 1 time unit at a time.

By its very nature, the equation you posted in post #1 is discrete. The continuous analog would be something like this:
$$f(t + \Delta t) = rf(t)(1 - f(t))$$
Unlike the original equation, where $n \in \{0, 1, 2, \dots \}$, t and $\Delta t$ could be considered to be elements of the reals.

Furthermore, the differential equation in the image you posted doesn't relate directly to the original equation. There's a big difference between dN/dt and N vs. $x_{n + 1}$ and $x_n$.

I'm not sure what you're trying to do in this thread.

 

[aheight]

Summary:: Recursive equations as composite equations

Hello,

I am trying to better understand the following discrete, recursive equation (logistic equation):
$$x_{n+1} =r x_n (1- x_n)$$
Is this an equation with two variables, $x$ and $t$, where $t$ assumes discrete values, or is it an equation with one single variable, the variable $x$? Is it a composite function?

It's an iteration expression with the previous output fed-back into the input. r is a constant which generally ranges from 0 to 4. And usually start the iteration by letting $x_0=0.2$. Suppose let r=3.2. Then if $x_0=0.2$, then $x_1=3.2(0.2)(1-0.2)=0.512$. So that $x_2=3.2(0.512)(1-0.512)=0.799$ and so forth. The points will oscillate between a set of "cyclic" points for certain values of r and become chaotic in another range. Now do this iteration scheme for say 500 times and take the last 100 terms ($x_{400},x_{500}$) and plot those points with r ranging from 0 to 4. You'll see the Feigenbaum plot with period-doubling. Here's a simple Mathematica code to show this:

r1 = Table[i, {i, 0.1, 4, 0.001}];
sol = Table[
   RecurrenceTable[{x1[t + 1] == r1[[i]] (1 - x1[t]) x1[t],
     x1[0] == 0.2}, x1, {t, 1000}], {i, Length[r1]}];

list1 = Table[{r1[[i]], sol[[i]][[-5 ;;]]} // Thread, {i,
     Length[sol]}] // Flatten[#, 1] &;

ListPlot[list1, AxesLabel -> {"r", "N"},
PlotRange -> {{0.1, 4}, {0.1, 1}}]

 

[fog37]

So the equation is recursive equation.

If we plotted $x$ versus $n$ (interpreting $n$ as $t$), we would see the variable $x$ oscillate in time and be periodic when $r=3.4$.Is it possible to retrieve the equation that produces the graph $x$ versus $n$?

 

[fog37]

Not necessarily. A sequence is a function that maps the non-negative integers to the reals. So in a sequence, the difference between two successive indexes is always 1, whereas times don't have to increase 1 second or 1 minute or 1 time unit at a time.

By its very nature, the equation you posted in post #1 is discrete. The continuous analog would be something like this:
$$f(t + \Delta t) = rf(t)(1 - f(t))$$
Unlike the original equation, where $n \in \{0, 1, 2, \dots \}$, t and $\Delta t$ could be considered to be elements of the reals.

Furthermore, the differential equation in the image you posted doesn't relate directly to the original equation. There's a big difference between dN/dt and N vs. $x_{n + 1}$ and $x_n$.

I'm not sure what you're trying to do in this thread.

Thanks, Mark44.

I find the discrete equation I initially presented very interesting (since it can generate deterministic chaos) and I am trying to understand it the best I can.

Any sequence is a function with the domain being the positive integers excluding 0. For example, the sequence $$f(n) = 4n-3$$
is a function in explicit form. Its recursive form is:
$$ f(1)=1$$ and $$f(n)=f(n-1)=+4$$
So in the case of the recursive equation I introduced, we are therefore dealing with a sequence in its recursive form $f(n+1) = rf(n)(1 - f(n))= rf(n) - f(n)^2$ and we can find its explicit form (which I am trying to find but struggling).

Does every discrete function $f(n)$ in explicit form has a recursive form? I would think so.

thanks

 

[Stephen Tashi]

Does every discrete function $f(n)$ in explicit form has a recursive form? I would think so.

The challenge in many math questions is to formulate them so they have nontrivial answers. Would you consider $f(n+1) = f(n+1) - f(n) + f(n)$ to be a "recursive form"?

To make the question non-trivial, we can try:
Is each sequence $\{a_n\}$ the unique solution to some recursion relation with a finite number of given initial conditions?

This still requires some refinement of the specifics of a "recursion relation". If we allow a recursion relation involving the unknown function $f(n)$ to explicitly have terms that depend on $n$, I think we again get a trivial answer.

 

[aheight]

So the equation is recursive equation.

If we plotted $x$ versus $n$ (interpreting $n$ as $t$), we would see the variable $x$ oscillate in time and be periodic when $r=3.4$.Is it possible to retrieve the equation that produces the graph $x$ versus $n$?

Not sure how it's being interpreted above but the Logistic equation as written is an iterated function: Iterated Functions
There is no "t" in my understanding.

The function being iterated is $f(x)=r x(1-x)$ and is composed with itself $f(f(\cdots)\cdots f)$

You can if you wish compute the iterated (composed) functions to some level of $n$ via NestList in mathematica. Below is $f$, $f(f)$, and $f(f(f))$:

myFun[x_] = 3.3 x (1 - x);
myEqns2 = NestList[myFun, x, 3]//Expand

$\begin{align*} &3.3 x-3.3 x^2\\ &-35.937 x^4+71.874 x^3-46.827 x^2+10.89 x\\ &-4261.84 x^8+17047.4 x^7-28154. x^6+24796.2 x^5-12520.6 x^4+3602.83 x^3-545.883 x^2+35.937 x \end{align*}$

Note in this example, if you computed the 10th composition (iteration) at x=0.2 and the 11th composition at x=0.2, you would find iteration 10 and 11 are beginning to cycle between the two values in the plot.

 

[fog37]

The challenge in many math questions is to formulate them so they have nontrivial answers. Would you consider $f(n+1) = f(n+1) - f(n) + f(n)$ to be a "recursive form"?

To make the question non-trivial, we can try:
Is each sequence $\{a_n\}$ the unique solution to some recursion relation with a finite number of given initial conditions?

This still requires some refinement of the specifics of a "recursion relation". If we allow a recursion relation involving the unknown function $f(n)$ to explicitly have terms that depend on $n$, I think we again get a trivial answer.

Hello. that is deeper than I thought :)

If an the equation involves $f(x)$ and the same function $f$ at a different location (time or space), like $f(x-1)$ then there should be some recursion going on.

Even a simple function like $f(x)=x^2$ should exhibit recursion, I believe, in the sense that the function connects its values with the values coming before them.
Sequences like ${a_n}$ are recursive if a recursion formula exists, as well as an explicit formula $a(n)$, that ties one specific element of the sequence to the one coming before it.

I can see how not every sequence would be recursive though.

 

[Mark44]

Even a simple function like $f(x)=x^2$ should exhibit recursion, I believe, in the sense that the function connects its values with the values coming before them.

No, $f(x)=x^2$ is not recursive. To find any function value, all you need is the x value in question. For a recursive function, to find the value of the function at a particular value, you have to evaluate the function at some other value. A simple example is the factorial function: f(n) = n*f(n - 1), with f(0) defined to be 1.
To find f(2), say, you need to evaluate f(1) and f(0).

Sequences like ${a_n}$ are recursive if a recursion formula exists, as well as an explicit formula $a(n)$, that ties one specific element of the sequence to the one coming before it.

No, a sequence is recursive if it is defined in terms of itself. The sequence in post #1 of this thread is recursive.

 

[Stephen Tashi]

No, $f(x)=x^2$ is not recursive.

Writing $f(x)$ as $f(x) = x^2$ does not express $f(x)$ in a recursive fashion. However, to say the function itself is "not recursive" seems to imply that there is no way of expressing that function as a recursion when we are given complete freedom in chosing how to express it.

Whether a function can be expressed in a recursive manner is (to me) a more interesting mathematical question than whether one way of writing it is called recursive.

 

[Stephen Tashi]

I can see how not every sequence would be recursive though.

I'm unsure.

As an example, if $f(n)$ is a function $G$ of $f(n-1), f(n-2), f(n-3)$ and the sequence contains the consecutive terms 4,6,3,2 then it cannot contain the consecutive terms 7,6,3,2 at later indices because the function $G$ cannot map 6,3,2 to both 4 and 7.

So to imagine a sequence that cannot be expressed recursively, I try to imagine a sequence with periods of ever increasing lengths that are separated by terms of different values.

For example: 4, 4,2, 7,2, 4,2,3, 7,2,3, 4,2,3,4, 7,2,3,4,...

 

[Mark44]

Writing $f(x)$ as $f(x) = x^2$ does not express $f(x)$ in a recursive fashion.

Which is exactly what we're talking about in this thread, not whether a function can possibly be expressed in a recursive manner.

 

[Stephen Tashi]

Which is exactly what we're talking about in this thread, not whether a function can possibly be expressed in a recursive manner.

That can be what you want to talk about. The question in post #7 is

Does every discrete function $f(n)$ in explicit form has a recursive form? I would think so.

 

[Mark44]

Even a simple function like $f(x)=x^2$ should exhibit recursion, I believe, in the sense that the function connects its values with the values coming before them.

Possibly the first sentence above isn't as clear as it should be. I interpreted "should exhibit recursion" to mean that it was in fact recursive.

 

[Stephen Tashi]

Yes, we need to clarify:

Even a simple function like $f(x)=x^2$ should exhibit recursion, I believe, in the sense that the function connects its values with the values coming before them.

For example, $f(x) = x^2$ satisfies $f(x) = 2f(x-1) - f(x-2) + 2$ with the initial condition $f(1) = 1$.

But to say that $f(x) = x^2$ "exhibits recursion", do we only require that it is one of many possible solutions to a recurrence relation? Or do we mean that it is a unique solution? - or a unique solution among the set of continuous solutions? - or unique among differentiable solutions? etc.

 

[fog37]

Yes, we need to clarify:



For example, $f(x) = x^2$ satisfies $f(x) = 2f(x-1) - f(x-2) + 2$ with the initial condition $f(1) = 1$.

But to say that $f(x) = x^2$ "exhibits recursion", do we only require that it is one of many possible solutions to a recurrence relation? Or do we mean that it is a unique solution? - or a unique solution among the set of continuous solutions? - or unique among differentiable solutions? etc.

Interesting. I didn't know that.

Just to paraphrase, so I understand clearly, let's keep considering the function like $f(x) = x^2$. The dependent values of this function satisfies the specific recursive equation $f(x) = 2f(x-1) - f(x-2) + 2$ with the initial condition $f(1) = 1$.
If we changed the initial condition, that specific recursive equation would not work anymore, correct?

In this case, the recursive equation starts at positive $x=1$ (the seed) and provides the values of $f(x)$ for subsequent integer values of $x$. The equation $f(x) = x^2$, on the other hand, exists for both continuous and discrete positive and negative values of $x$.

Could a different "initial condition+recursive equation" represent the same function
$f(x) = x^2$? I would think so...

My sense is that if we have an equation $f(x)$, we can always find a specific pair [recursive equation + initial condition] that matches the the values generated by $f(x)$ starting from $x=1$..

Also, the initial condition is not limited to start at $x=1$, correct? We could have $f(-2)= initial value$, correct?

 

[Stephen Tashi]

Interesting. I didn't know that.

Ok, but you didn't answer the question. From reading your posts, I gather that you have only studied mathematics from an informal and intuitive point of view. That's where everyone starts out. Answering the question precisely requires understanding math rigorously. You may not be ready to do that.

Just to paraphrase, so I understand clearly, let's keep considering the function like $f(x) = x^2$. The dependent values of this function satisfies the specific recursive equation $f(x) = 2f(x-1) - f(x-2) + 2$ with the initial condition $f(1) = 1$.
If we changed the initial condition, that specific recursive equation would not work anymore, correct?

If by "not work", you mean that $f(x) = x^2$ might no longer be a solution then, yes, that is correct. However some conditions like $f(2) = 4$ still allow $f(x) = x^2$ to be a solution.

In this case, the recursive equation starts at positive $x=1$ (the seed) and provides the values of $f(x)$ for subsequent integer values of $x$.

Often, when you compute values for a function $f(x)$ using a recursive equation, you began the calculation at $x = 2$ having been given the value of $f$ at $x = 1$. This is because recursive equations are often (but not always) meant to apply only for positive integer values of $x$. Is that what you mean? The equation itself doesn't "start" at a particular value of $x$.

The equation $f(x) = x^2$, on the other hand, exists for both continuous and discrete positive and negative values of $x$.

It is possible to write recursive equations with the understanding that the argument of the function can be any real number. The person writing the equation should make it clear if that is the case. Sometimes the domain of a function is implied by the general context where it appears. There is no hard and fast rule that a recursive equation applies only to discrete or integer values.

Could a different "initial condition+recursive equation" represent the same function
$f(x) = x^2$? I would think so...

You have to define what you mean by "represent". To do that, you must first understand why the informal use of the word "represent" is ambiguous. Equations can have several different solutions.

My sense is that if we have an equation $f(x)$, we can always find a specific pair [recursive equation + initial condition] that matches the the values generated by $f(x)$ starting from $x=1$..

It's unclear what you mean by "have an equation". If we set $f(x)$ equal to the outcome of a computer algorithm whose input is $x$, do we "have an equation" for it? A computer algorithm can compute the terms for the sequence given in post #13.

Also, the initial condition is not limited to start at $x=1$, correct? We could have $f(-2)= initial value$, correct?

Yes, it's correct that an "initial condition" might ( or might not) be given for values of a function when the argument is -2, or other numbers different than 1. It depends on the full context of where the equation appears.

Trying to deduce the meaning of a single equation without considering the context where it appears is like trying to interpret the sentence "It is better than the other thing" without seeing the context where it is written.

 

[DaveE]

Summary:: Recursive equations as composite equations

If time was not discrete but continuous, how would the equation look like? Would it be x(t)=rx(t−1)[1−x(t−1)]? I don't think so...

The continuous form is a non-linear differential equation.

dx/dt = rx(1-x/k) with r,k constant. x(t) a function of continuous time.

There's lots of stuff on the web about this subject. Like this short piece.