4
$\begingroup$

I encountered an interesting inequality that I'm not sure how to approach. Here $c$ is a positive constant. $$f(n+1) - f(n) = c f(n)\sum_{m=0}^n f(m)$$

I am not familiar with techniques to solve recursive equations, so I thought about a similar differential equation of it $$\frac{\partial f}{\partial x} = cf(x)\int_{z=0}^x f(z)dz.$$

I am quite new to the topic of differential equations though, so I might be missing some obvious techniques to solve this kind of equality. With my limited knowledge I tried applying Laplace transform or the Fourier transform to this equation to no avail, but the expression looks nice enough that I suspect there is an analytical solution to it. Any help to getting an analytical expression of this equation is much appreciated!

(This is coming from a real-world problem, so for now, any "nice" assumption on $f$ and the initial conditions and so on can be placed)

$\endgroup$
10
  • $\begingroup$ An inequality does not define a sequence, so you can't "solve" it. $\endgroup$
    – dxiv
    May 20 at 22:40
  • $\begingroup$ @dxiv Do you mean I am missing initial conditions? Or assumptions on $f$? This is coming from an engineering problem so any nice assumption on $f$ to make the math go through is fine. $\endgroup$
    – Nen
    May 20 at 22:43
  • 1
    $\begingroup$ What I meant is that the inequality does not define the sequence univocally, so it is pointless to try to "solve" it. Take for example a trivial inequality $\,f_{n+1} - f_n \ge 1\,$, then either of $\,f_n = n\,$, $\,f_n = n^2\,$ or $\,f_n = 2^n\,$ satisfies it. There is no unique solution, so you can't "solve" it. $\endgroup$
    – dxiv
    May 20 at 22:49
  • $\begingroup$ @dxiv Ok, but I'm only interested in the expression of $f_n$ that grows the slowest, is that impossible to obtain in the current context? $\endgroup$
    – Nen
    May 20 at 22:53
  • $\begingroup$ Replace the $\,\ge\,$ with an $\,=\,$, if that's what you meant to ask. Then the question becomes a legitimate one, though it's unilkely that a closed form solution exists. $\endgroup$
    – dxiv
    May 20 at 22:58

2 Answers 2

7
$\begingroup$

Your question comes in two variants. One is discrete. The other continuous.

The discrete variant asks about the equation $$ f(n+1) - f(n) = c f(n)\sum_{m=0}^n f(m). \tag{1} $$ A nicer version of this is to define $$ a_n := c f(n), \qquad b_n := 1 + \sum_{m=0}^n a_m. \tag{2} $$ Multiply equation $(1)$ by $\,c\,$ to get $$ a_{n+1} = a_n + a_n\sum_{m=0}^n a_m = a_n b_n = a_0\prod_{m=0}^n b_m \tag{3} $$ where the initial value $\,a_0\,$ is arbitrary. A simple example is if $\,a_0=1.\,$ This is OEIS sequence A001697. The growth rate is given as $\,a_n \sim c^{2^n}\,$ where $\,c \approx 1.335245.\,$ This is the typical growth rate with a different constant for each choice of $\,a_0.\,$ I don't think there is a known closed form.


The continuous variant asks about the related differential equation $$ \frac{\partial f}{\partial x} = cf(x)\int_{z=0}^x f(z)dz. \tag{4} $$ This is more interesting. The equation is equivalent to $$ \frac{\partial g}{\partial x} = c\int_{z=0}^x e^{g(z)}dz \;\; \text{ where } \;\; g(x) := \log(f(x)). $$ Assuming $\,g(x)\,$ has a power series, let $$ g(x) = a_0 + a_2\frac{x^2}{2!} + a_4\frac{x^4}{4!} + \cdots $$ where $\,c = a_2/e^{a_0}.\,$ For simplicity assume that $\,a_0=0, a_2=1.\,$ The solution of equation $(4)$ is $$ f(x) = \sec\left(\frac{x}{\sqrt{2}}\right)^2 = 1\frac{x^2}{2!} +4\frac{x^4}{4!} +34\frac{x^6}{6!} + \cdots $$ where the coefficients are OEIS sequence A002105.

$\endgroup$
3
  • $\begingroup$ very clever approach ! $\endgroup$
    – G Cab
    May 21 at 23:25
  • $\begingroup$ +1 Shouldn't equation (2) be $a_n:=cf(n)$? $\endgroup$ May 22 at 18:38
  • $\begingroup$ @EliBartlett Oops! Thanks for that correction. $\endgroup$
    – Somos
    May 22 at 19:45
1
$\begingroup$

Being a combination of product and sum, it looks difficult that there might be a closed form.

The best I can suggest is to make the substitution

$$ f(n) = 2^{g(n)} $$ I am using $2$ as a base because $2^n$ has a simple difference.

Then $$ \eqalign{ & f(n + 1) - f(n) = 2^{g(n + 1)} - 2^{g(n)} = 2^{g(n)} \left( {2^{g(n + 1) - g(n)} - 1} \right) \cr & 2^{g(n)} \left( {2^{g(n + 1) - g(n)} - 1} \right) = c2^{g(n)} \sum\limits_{k = 0}^n {2^{g(k)} } \cr & 2^{g(n + 1) - g(n)} = 1 + c\sum\limits_{k = 0}^n {2^{g(k)} } \cr & 2^{g(n + 2) - g(n + 1)} - 2^{g(n + 1) - g(n)} = c2^{g(n + 1)} \cr & 2^{g(n + 2) - 2g(n + 1)} - 2^{ - g(n)} = c \cr & \left( {2^{g(n + 2) - 2g(n + 1) + g(n)} - 1} \right)2^{ - g(n)} = c \cr & 2^{\Delta ^2 g(n)} = 1 + c2^{g(n)} \cr & 2^{\Delta ^2 g(n)} = 1 + 2^{\ln c + g(n)} \cr & \approx \Delta ^2 g(n) + g(n) = \ln c\quad \left| {\;1 < < 2^{g(n)} } \right. \cr} $$

So the asymptotics is clear.

$\endgroup$

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.