4
$\begingroup$

Problem. Let $(f_n)_{n=1}^\infty$ be a sequence of functions $f_n\colon [-1,\infty)^n\to\mathbb{R}$ that are recursively defined in the following way:

$$f_1(x_1)=1+x_1,$$

$$f_n(x_1,\ldots,x_n) = \begin{cases} (1+x_n)f_{n-1}(x_1,\ldots,x_{n-1}) & \text{if } f_{n-1}(x_1,\ldots,x_{n-1}) \le 1, \\ x_n + f_{n-1}(x_1,\ldots,x_{n-1}) & \text{otherwise}. \end{cases}$$

Let $(g_n)_{n=1}^\infty$ be a sequence of functions $g_n\colon [-1,\infty)^n\to\mathbb{R}$ that are defined in the following way:

$$g_n(x_1,\ldots,x_n) = \prod_{k=1}^n (1+x_k).$$

Show, for any $n\ge1$ and any $x_1,\ldots,x_n\in[-1,\infty)$, that if $f_n(x_1,\ldots,x_n) <1$, it also holds that $g_n(x_1,\ldots,x_n) \le1$.

Observations. I have tried doing this with induction, but that doesn’t seem to work. It appears that I need more intricate knowledge of the relationship between $f_n$ and $g_n$ in order to solve the problem. Clearly, both are multivariate polynomials. It also seems like all the terms in $f_n$ are also contained in $g_n$, but I don’t know how that could help.

Real-life motivation. Note that the quantity $g_n(x_1,\ldots,x_n)$ is nothing but 1 dollar that has been invested in $n$ different ventures with percentage returns (positive or negative) of $x_1,\ldots,x_n$, where the profits from each venture have been reinvested in the next venture. The quantity $f_n(x_1,\ldots,x_n)$ is similar, except that profits are not reinvested. The objective is to show that if investing in ventures without reinvesting profits results in a loss, then reinvesting the profits couldn’t possibly have resulted in a profit.

  • 1
    You might want to add the assumption that $x_n\ge-1$ so that an investor doesn't lose more than they invest.2011-10-13
  • 0
    Yeah, we can safely add this assumption. I have modified my question accordingly.2011-10-15

3 Answers 3

3

As Gortaur suggests, some additional restriction is necessary:

$f_1(3/2)=1+3/2=5/2$

$f_2(3/2,-2)=-2+5/2=1/2$

$f_3(3/2,-2,-2)=(1+(-2))(1/2)=-1/2<1$

$g_3(3/2,-2,-2)=(3/2+1)(-2+1)(-2+1)=5/2>1$

  • 1
    I would think that $x_n\ge-1$ would be a reasonable assumption since I don't think in many schemes does one lose more than they invest.2011-10-13
  • 0
    Thanks dfeuer, you're right. The “$x_i\ge-1$” assumption has been added to the original question now.2011-10-15
  • 0
    @Topology: to notify dfeuer of a comment, put `@dfeuer` into the comment.2011-10-16
4

Define $\varphi(x)$ by $$ \varphi(x)=\left\{\begin{array}{}x&\text{if }x\le1\\\exp(x-1)&\text{if }x>1\end{array}\right.\tag{1} $$ Note that $\varphi$ is monotonic increasing and $x\le\varphi(x)$ for all $x$.

Claim: $$ (1+x)\varphi(y)\le\left\{\begin{array}{}\varphi((1+x)y)&\text{if }y\le1\\\varphi(x+y)&\text{if }y>1\end{array}\right.\tag{2} $$ Proof:

If $y\le1$, then $(1+x)\varphi(y)=(1+x)y\le\varphi((1+x)y)$.

If $y>1$ and $x+y>1$, then $(1+x)\varphi(y)\le\exp(x)\varphi(y)=\varphi(x+y)$.

If $y>1$ and $x+y\le1$, then $(1+x)\varphi(y)-\varphi(x+y)=(1+x)\exp(y-1)-(x+y)$.

As a function of $x$, $(1+x)\exp(y-1)-(x+y)$ is linear with a slope of $\exp(y-1)-1>0$. Thus, it reaches its maximum at $x=1-y$, but then $$ \begin{align} (1+x)\exp(y-1)-(x+y) &\le\exp(x)\exp(y-1)-(x+y)\\ &=\exp(x+y-1)-(x+y)\\ &=0 \end{align} $$ Therefore, $(1+x)\varphi(y)\le\varphi(x+y)$. $$\Box$$ So that no one loses more than they invest, I will assume $x_k\ge-1$.

Note that $g_0=\varphi(f_0)=1$. Suppose that $g_{n-1}\le\varphi(f_{n-1})$, then

if $f_{n-1}\le1$, then $g_n=(1+x_n)g_{n-1}\le(1+x_n)\varphi(f_{n-1})\le\varphi((1+x_n)f_{n-1})=\varphi(f_n)$.

if $f_{n-1}>1$, then $g_n=(1+x_n)g_{n-1}\le(1+x_n)\varphi(f_{n-1})\le\varphi(x_n+f_{n-1})=\varphi(f_n)$.

Thus, $g_n\le\varphi(f_n)$.

Conclusion: Perhaps I should add that this says that when $f_n\le1$ we have $g_n\le f_n$.

3

So, you have $$ f_{i+1} = f_{i}+\min\{f_i,1\}x_{i+1} $$ and $$ g_{i+1} = g_i+g_ix_{i+1} $$ with $f_0=g_0=1$. We assume from now that $x_i\geq 0$.

The idea is to consider separately intervals for positive or negative rates $x_i$ because on each such interval the dynamics of $f_i$ is simple. We put $$ 0=\tau_0<\sigma_1<\tau_1<\sigma_2<\tau_2<... $$ where for $k\in \mathbb N$ we define $\sigma_{k} = \inf\{i>\tau_{k-1}:f_i<1\}$ and $\tau_k = \inf\{i>\sigma_{k}:f_i\geq 1\}$. It means that $\sigma_1$ will be the first time $f$ will go below $1$ after $\tau_0=0$, $\tau_1$ - the first time $f$ will go above $1$ after $\sigma_1$; $\sigma_2$ is the first time $f$ goes below $1$ after $\tau_1$ etc.

Let us formulate the fact we use, it is proved below. For all $k \geq 0$ it holds that $$ \begin{cases} \text{if }g_{\tau_k}\leq f_{\tau_k}&\text{ then }g_{\sigma_{k+1}}\leq f_{\sigma_{k+1}},\quad(*) \\ \text{if }g_{\sigma_{k+1}}\leq f_{\sigma_{k+1}}&\text{ then }g_{\tau_{k+1}}\leq f_{\tau_{k+1}}.\quad (**) \end{cases} $$

Suppose, the statement $(*),(**)$ is true. Since $g_{\tau_0} =g_0\leq f_0=f_{\tau_0}$, we have based on the statement above: $g_{\tau_k}\leq f_{\tau_k}$ and $g_{\sigma_{k+1}}\leq f_{\sigma_{k+1}}$ for all $k\geq 0$ $(***)$.

Let's show that it implies your statement: for all $i\geq 0$ it holds that $f_i<1\Rightarrow g_i\leq 1$.

  1. If $\tau_k \leq i<\sigma_{k+1}$ for some $k\geq 0$ (the interval without reinvestment) then $f_i\geq 1$ and your statement is true.

  2. If $\sigma_k \leq i<\tau_k$ for some $k\geq 1$ (the interval with reinvestment) then we have: $g_{\sigma_k}\leq f_{\sigma_k}<1$ by $(***)$. Moreover, the dynamics of $g$ and $f$ is the same on this interval, so $$ \frac{g_i}{f_i} = \frac{g_{\sigma_k}}{f_{\sigma_k}} $$ on this interval and hence $g_i\leq f_i<1$.

We had consider all possible cases for $n$ and proved even stronger statement: if $f_i<1$ then $g_i\leq f_i$. We only need to prove $(*)$ and $(**)$ now.


We first prove $(*)$. Consider arbitrary $k\geq 0$ and for the shorthand let us denote $\tau_k = m$, $\sigma_{k+1}=n>m$ and we suppose as in $(*)$ that $g_m\leq f_m$.

  1. if $n = m+1$ then $f_m\geq 1$ but $f_{m+1} = f_m+x_{m+1}<1$ so $-1

  2. suppose now that $n>m+1$ and denote $j = n-m-1>0$. So, $f_{m+i}\geq 1$ for all $0\leq i\leq j$ but $f_{m+j+1} = f_{n} <1$. Recall that $$ f_{m+j} = f_m+\sum\limits_{i=1}^j x_{m+i}=: f_m+a. $$ On the other hand, $$ g_{m+j} = g_m\prod\limits_{i=1}^j(1+x_{m+i})\leq g_m \exp\left\{\sum\limits_{i=1}^j x_{m+i}\right\} = g_m\mathrm e^{a}. $$ As a result we have: $$ g_n = g_{m+j+1} = g_{m+j}(1+x_n)\leq g_m\mathrm e^a(1+x_n)\leq f_m\mathrm e^a(1+x_n)\leq f_m+a+x_n = f_n $$ Here we used conditions $f_m\geq 1,a\geq 0,-1

The proof of $(**)$ is much easier. If $g_{\sigma_{k+1}}\leq f_{\sigma_{k+1}}$ then unless $i<\tau_{k+1}$ you will always reinvest in both cases and $f,g$ will differ only by the same multiplier. That's why $g_{\tau_{k+1}}\leq f_{\tau_{k+1}}$.

  • 0
    No, $f_3=3+1\cdot0.3=3.3$ and $g_3=4(1+0.3)=5.2$2011-10-13
  • 0
    @AD: thanks for fixing my typo, I mixed $x$ and $1+x$.2011-10-13
  • 0
    No problem. Maybe you should check the new numbers as well. :)2011-10-13
  • 0
    Thanks for your idea on how to write $f_n$ in a simpler way. However, your example doesn’t work out because $f_3$ actually ends up being $2.3$ for $x_1=x_2=1$ and $x_3=-0.7$.2011-10-13
  • 0
    @Topology: you're certainly right, sorry. Doing strange mistakes today. Getting interesting.2011-10-13
  • 0
    @Topology: seems that you're right with your statement. I put some ideas there which are sufficient for the proof but may be imprecise.2011-10-13
  • 0
    @Topology: I proved even that $f<1$ implies $g\leq f$ trying to be as explicit as possible. However, some inequalities in this proof may be unclear, so please let me know if I should explain them.2011-10-14
  • 1
    You claim in several places that $x_k>-1$. It has been suggested in a couple of comments, but it should probably be mentioned in the proof. $$ $$ In the proof of $(*)$, section 2., it is recalled that $x_{m+i}>0$ for all $1\le i\le j$. This is not necessarily so. We only know that $f_m\ge1$ and $f_{n-1}\ge1$ so we don't even know that $a=f_{n-1}-f_m>0$. $$ $$ The whole part about arithmetic and geometric averages can be replaced with the fact that $\displaystyle\prod_{i=1}^j(1+x_{m+i})\le e^{\sum_{i=1}^jx_{m+i}}$.2011-10-14
  • 1
    The conditions used include $f_m\ge1$, $a\ge0$ (which we don't know), and $-11$ so the range $-1$$ $$ We do know that $f_m+a=f_{n-1}\ge1$ and $f_m+a+x_n=f_n<1$. So the range you may have intended above might be $-12011-10-14
  • 0
    I don't see how to get $f_me^a(1+x_n)\le(f_m+a+x_n)$.2011-10-14
  • 1
    Ah, when $x_n=-1$ the left side is $0$ and the right side is $f_n\ge0$. When $x_n=1-f_m-a$, the right side is $1$ and the left side is $f_me^a(2-f_m-a)\le e^a(1-a/2)^2\le1$ since $(1-a/2)\le e^{-a/2}$.2011-10-14
  • 0
    @robjohn: thanks, I'm happy that we agreed2011-10-14
  • 1
    I made a mistake in my last comment, when $x_n=-1$, the right side is $f_{n-1}-1\ge0$. Things are still okay, though. :-)2011-10-15
  • 1
    Having shown the last inequality, all of my other comments above are easily correctable, so your answer will work. (+1)2011-10-15
  • 0
    @robjohn: thank you so much - I hope I manage to correct them tomorrow2011-10-15
  • 0
    I still don’t see why $f_me^a(1+x_n)\le f_m+a+x_n$. In an earlier comment, @robjohn considered two cases where the inequality holds. But why does it hold in general?2011-10-15
  • 1
    @Topology: $f_me^a(1+x_n)-f_m+a+x_n$ is linear in $x_n$. If we can show that it is $\le0$ at both ends of the possible range, then it is $\le0$ everywhere in the possible range.2011-10-15
  • 0
    @robjohn Ah, of course. But another thing: How did you obtain $f_me^a(2-f_m-a)\le e^a(1-a/2)^2$ above? What happened to the $f_m$?2011-10-16
  • 1
    @Topology: $f_me^a(2-f_m-a)$ is quadratic in $f_m$. Find the $f_m$ that maximizes it and it gives $e^a(1-a/2)^2$ as the maximum.2011-10-16
  • 0
    @robjohn I'm starting to have second thoughts about $f_me^a(1+x_n)\le f_m+a+x_n$. Just testing these two extreme cases for $x_n$ doesn't look right because it is not "independent" from the other quantities, $a$ and $f_m$, which must change if $x_n$ is changed (despite some inequality relationships that hold between them). In order to do this properly, I would think that we should show, beyond any doubt, that $f_me^a(1+x_n) - (f_m+a+x_n)\le 0$. While trying this, one ends up with something not quite as nice, when maximizing the less pretty function of $f_m$ one ends up with. Ideas?2011-10-18
  • 1
    $x_n$ is only dependent on $f_m$ and $a$ in so far as $-1\le x_n\le1-f_m-a$. $x_n$ can be any value in that range. In any case, all we need to verify is the inequality $f_me^a(1+x_n)\le f_m+a+x_n$. Since both sides are linear in $x_n$, if we verify the inequality at both ends ($-1$ and $1-f_m-a$), it is verified everywhere in between.2011-10-18